https://codeforces.com/contest/1101/problem/C
C++版本一
题解:
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
struct Node
{
int l;
int r;
int id;
int f;
}ed[N];
bool cmp(const Node &x,const Node &y)
{
if (x.l!=y.l) return x.l<y.l;
return x.r<y.r;
}
bool cmp2(const Node &x,const Node &y)
{
return x.id<y.id;
}
int main()
{
scanf("%d",&t);
while (t--)
{
int flag=0;
scanf("%d",&n);
for (int i=1;i<=n;++i)
{
scanf("%d%d",&ed[i].l,&ed[i].r);
ed[i].id=i;
}
sort(ed+1,ed+n+1,cmp);
int a;
a=ed[1].r;
ed[1].f=1;
for (int i=2;i<=n;++i)
{
if (!flag)
{
if (ed[i].l<=a) a=max(a,ed[i].r),ed[i].f=1;
else
{
flag=1;
ed[i].f=2;
}
}
else ed[i].f=2;
}
if (!flag) printf("-1\n");
else
{
sort(ed+1,ed+n+1,cmp2);
for (int i=1;i<=n;++i)
{
printf("%d ",ed[i].f);
}
printf("\n");
}
}
}
C++版本二
题解:根据题意两组区间不能有交集。所以至少有两块独立的合并后区间。
/*
*@Author: STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,q;
int ans,cnt,flag,temp;
struct node{
int l,r,id,f;
bool operator <(const node &S)const{
if(l==S.l)
return r<S.r;
return l<S.l;
}
}e[N];
int c[N<<1];
char str;
int main()
{
#ifdef DEBUG
freopen("input.in", "r", stdin);
//freopen("output.out", "w", stdout);
#endif
//
scanf("%d",&t);
while(t--){
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d%d",&e[i].l,&e[i].r);
e[i].id=i;
}
sort(e+1,e+n+1);
int pos=e[1].r;
flag=1;
c[e[1].id]=1;
q=1;
for(int i=2;i<=n;i++){
if(pos<e[i].l){
flag=0;
if(q==1)
q=2;
else
q=1;
}
c[e[i].id]=q;
pos=max(pos,e[i].r);
}
if(flag){
printf("-1\n");
continue;
}
for(int i=1;i<n;i++){
printf("%d ",c[i]);
}
printf("%d\n",c[n]);
}
//cout << "Hello world!" << endl;
return 0;
}