oj.uz

Submission #63213

# Submission time Handle Problem Language Result Execution time Memory
63213 2018-08-01T06:06:19 Z 정원준(#1835) Alternating Current (BOI18_alternating) C++11
0 / 100
 293 ms 17932 KB 
#include <bits/stdc++.h>
#define L int
#define inf 123456
using namespace std;

int ans[100010];
int n,m;
vector<int>v[100010],lines[100010];
int chk[100010];

struct S{
	int s,e,ord;
}a[100010];

int tr[400040],one[400040],two[400040];

int onetr[400040],twotr[400040];

void update(int now,int S,int E,int s,int e,int val,int num){
	if(S>e||E<s) return;
	if(s<=S&&E<=e)
	{
		tr[now]+=val;
		return;
	}
	int mid=(S+E)/2;
	update(now*2,S,mid,s,e,val,num);
	update(now*2+1,mid+1,E,s,e,val,num);
}

void initone(int now,int S,int E){
	one[now]=inf;
	if(S==E) return;
	int mid=(S+E)/2;
	initone(now*2,S,mid);
	initone(now*2+1,mid+1,E);
}
void updateone(int now,int S,int E,int s,int e,int val,int num){
	if(S>e||E<s) return;
	//printf("%d %d %d %d %d %d %d\n",now,S,E,s,e,val,num);
	if(s<=S&&E<=e)
	{
		one[now]=min(one[now],num);
		return;
	}
	int mid=(S+E)/2;
	updateone(now*2,S,mid,s,e,val,num);
	updateone(now*2+1,mid+1,E,s,e,val,num);
}
void updatetwo(int now,int S,int E,int s,int e,int val,int num){
	if(S>e||E<s) return;
	if(s<=S&&E<=e)
	{
		two[now]=max(two[now],num);
		return;
	}
	int mid=(S+E)/2;
	updatetwo(now*2,S,mid,s,e,val,num);
	updatetwo(now*2+1,mid+1,E,s,e,val,num);
}

int sum(int now,int S,int E,int loc){
	if(S>loc||E<loc) return 0;
	if(S==E) return tr[now];
	int mid=(S+E)/2;
	return tr[now]+sum(now*2,S,mid,loc)+sum(now*2+1,mid+1,E,loc);
}


int getone(int now,int S,int E,int loc){
	//printf("%d %d %d %d\n",now,S,E,loc);
	if(S>loc||E<loc) return inf;
	if(S==E) return one[now];
	int mid=(S+E)/2;
	return min(one[now],min(getone(now*2,S,mid,loc),getone(now*2+1,mid+1,E,loc)));
}


int gettwo(int now,int S,int E,int loc){
	//printf("%d %d %d %d\n",now,S,E,loc);
	if(S>loc||E<loc) return 0;
	if(S==E) return two[now];
	int mid=(S+E)/2;
	return max(two[now],max(gettwo(now*2,S,mid,loc),gettwo(now*2+1,mid+1,E,loc)));
}

void oneup(int now,int S,int E,int s,int e,int val){
	if(S>e||E<s) return;
	if(s<=S&&E<=e)
	{
		onetr[now]+=val;
		return;
	}
	int mid=(S+E)/2;
	oneup(now*2,S,mid,s,e,val);
	oneup(now*2+1,mid+1,E,s,e,val);
}

void twoup(int now,int S,int E,int s,int e,int val){
	if(S>e||E<s) return;
	if(s<=S&&E<=e)
	{
		twotr[now]+=val;
		return;
	}
	int mid=(S+E)/2;
	twoup(now*2,S,mid,s,e,val);
	twoup(now*2+1,mid+1,E,s,e,val);
}

int oneget(int now,int S,int E,int loc){
	if(S>loc||E<loc) return 0;
	if(onetr[now]) return 1;
	if(S==E) return 0;
	L mid=(S+E)/2;
	return oneget(now*2,S,mid,loc)||oneget(now*2+1,mid+1,E,loc);
}
int twoget(int now,int S,int E,int loc){
	if(S>loc||E<loc) return 0;
	if(twotr[now]) return 1;
	if(S==E) return 0;
	L mid=(S+E)/2;
	return twoget(now*2,S,mid,loc)||twoget(now*2+1,mid+1,E,loc);
}

void E(){
	puts("impossible");
	exit(0);
}

void dfs(int x,int col){
	int i;
	ans[x]=col;
	for(i=0;i<v[x].size();i++)
	{
		if(ans[v[x][i]]==col) E();
		if(chk[v[x][i]])
		{
			chk[v[x][i]]=0;
			dfs(v[x][i],3-col);
		}
	}
}

int main()
{
	srand((int)time(NULL));
	scanf("%d %d",&n,&m);
	L i,j;
	for(i=1;i<=m;i++)
	{
		scanf("%d %d",&a[i].s,&a[i].e);
		lines[a[i].s].push_back(i);
		a[i].ord=i;
		if(a[i].s<=a[i].e) update(1,1,n,a[i].s,a[i].e,1,i);
		else
		{
			update(1,1,n,1,a[i].e,1,i);
			update(1,1,n,a[i].s,n,1,i);
		}
	}
	initone(1,1,n);
	for(i=1;i<=m;i++)
	{
		if(a[i].s<=a[i].e) updateone(1,1,n,a[i].s,a[i].e,1,i);
		else
		{
			updateone(1,1,n,1,a[i].e,1,i);
			updateone(1,1,n,a[i].s,n,1,i);
		}
	}
	for(i=1;i<=m;i++)
	{
		if(a[i].s<=a[i].e) updatetwo(1,1,n,a[i].s,a[i].e,1,i);
		else
		{
			updatetwo(1,1,n,1,a[i].e,1,i);
			updatetwo(1,1,n,a[i].s,n,1,i);
		}
	}
	/*for(i=1;i<=4*n;i++)
	{
		printf("%lld %lld\n",i,one[i]);
	}*/
	
	for(i=1;i<=n;i++)
	{
		L temp=sum(1,1,n,i);
		if(temp<=1) E();
		else if(temp<=2)
		{
			L temp1=getone(1,1,n,i),temp2=gettwo(1,1,n,i);
			//printf("%d %d %d\n",i,temp1,temp2);
			v[temp1].push_back(temp2);
			v[temp2].push_back(temp1);
			chk[temp1]=chk[temp2]=1;
		}
	}
	for(i=1;i<=m;i++)
	{
		if(chk[i])
		{
			chk[i]=0;
			dfs(i,1);
		}
	}
	for(i=1;i<=m;i++)
	{
		if(ans[i]==1)
		{
			if(a[i].s<=a[i].e)
			{
				oneup(1,1,n,a[i].s,a[i].e,1);
			}
			else
			{
				oneup(1,1,n,1,a[i].s,1);
				oneup(1,1,n,a[i].e,n,1);
			}
		}
		else
		{
			if(a[i].s<=a[i].e)
			{
				twoup(1,1,n,a[i].s,a[i].e,1);
			}
			else
			{
				twoup(1,1,n,1,a[i].s,1);
				twoup(1,1,n,a[i].e,n,1);
			}
		}
		//printf("%d ",ans[i]);
	}
	for(i=1;i<=n;i++)
	{
		L temp1=oneget(1,1,n,i);
		L temp2=twoget(1,1,n,i);
		if(!temp1)
		{
			for(j=0;j<lines[i].size();i++)
			{
				if(!ans[lines[i][j]])
				{
					ans[lines[i][j]]=1;
					if(a[lines[i][j]].s<=a[lines[i][j]].e)
					{
						oneup(1,1,n,a[lines[i][j]].s,a[lines[i][j]].e,1);
					}
					else
					{
						oneup(1,1,n,a[lines[i][j]].s,n,1);
						oneup(1,1,n,1,a[lines[i][j]].e,1);	
					}
					break;
				}
			}
		}
		if(!temp2)
		{
			for(j=0;j<lines[i].size();i++)
			{
				if(!ans[lines[i][j]])
				{
					ans[lines[i][j]]=2;
					if(a[lines[i][j]].s<=a[lines[i][j]].e)
					{
						twoup(1,1,n,a[lines[i][j]].s,a[lines[i][j]].e,1);
					}
					else
					{
						twoup(1,1,n,a[lines[i][j]].s,n,1);
						twoup(1,1,n,1,a[lines[i][j]].e,1);	
					}
					break;
				}
			}
		}
	}
	for(i=1;i<=m;i++)
	{
		if(ans[i]==1) printf("0");
		else if(ans[i]==2) printf("1");
		else if(rand()%2) printf("0");
		else printf("1");
	}
	
}

Compilation message

alternating.cpp: In function 'void dfs(int, int)':
alternating.cpp:134:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<v[x].size();i++)
          ~^~~~~~~~~~~~
alternating.cpp: In function 'int main()':
alternating.cpp:241:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j=0;j<lines[i].size();i++)
            ~^~~~~~~~~~~~~~~~
alternating.cpp:261:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(j=0;j<lines[i].size();i++)
            ~^~~~~~~~~~~~~~~~
alternating.cpp:148:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
alternating.cpp:152:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&a[i].s,&a[i].e);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 7 ms 5224 KB Output is correct
3 Correct 6 ms 5224 KB Output is correct
4 Correct 7 ms 5324 KB Output is correct
5 Correct 7 ms 5388 KB Output is correct
6 Correct 7 ms 5388 KB Output is correct
7 Correct 7 ms 5388 KB Output is correct
8 Correct 7 ms 5388 KB Output is correct
9 Correct 7 ms 5388 KB Output is correct
10 Correct 7 ms 5388 KB Output is correct
11 Correct 9 ms 5388 KB Output is correct
12 Correct 8 ms 5388 KB Output is correct
13 Correct 7 ms 5388 KB Output is correct
14 Correct 7 ms 5388 KB Output is correct
15 Correct 7 ms 5388 KB Output is correct
16 Correct 5 ms 5388 KB Output is correct
17 Correct 5 ms 5388 KB Output is correct
18 Correct 8 ms 5388 KB Output is correct
19 Correct 6 ms 5388 KB Output is correct
20 Correct 6 ms 5388 KB Output is correct
21 Correct 7 ms 5388 KB Output is correct
22 Correct 7 ms 5388 KB Output is correct
23 Correct 6 ms 5388 KB Output is correct
24 Correct 6 ms 5388 KB Output is correct
25 Correct 6 ms 5388 KB Output is correct
26 Correct 6 ms 5388 KB Output is correct
27 Correct 6 ms 5388 KB Output is correct
28 Correct 6 ms 5388 KB Output is correct
29 Correct 7 ms 5388 KB Output is correct
30 Correct 6 ms 5388 KB Output is correct
31 Correct 9 ms 5388 KB Output is correct
32 Correct 7 ms 5388 KB Output is correct
33 Incorrect 6 ms 5388 KB no wires in direction 1 between segments 8 and 10
34 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 7 ms 5224 KB Output is correct
3 Correct 6 ms 5224 KB Output is correct
4 Correct 7 ms 5324 KB Output is correct
5 Correct 7 ms 5388 KB Output is correct
6 Correct 7 ms 5388 KB Output is correct
7 Correct 7 ms 5388 KB Output is correct
8 Correct 7 ms 5388 KB Output is correct
9 Correct 7 ms 5388 KB Output is correct
10 Correct 7 ms 5388 KB Output is correct
11 Correct 9 ms 5388 KB Output is correct
12 Correct 8 ms 5388 KB Output is correct
13 Correct 7 ms 5388 KB Output is correct
14 Correct 7 ms 5388 KB Output is correct
15 Correct 7 ms 5388 KB Output is correct
16 Correct 5 ms 5388 KB Output is correct
17 Correct 5 ms 5388 KB Output is correct
18 Correct 8 ms 5388 KB Output is correct
19 Correct 6 ms 5388 KB Output is correct
20 Correct 6 ms 5388 KB Output is correct
21 Correct 7 ms 5388 KB Output is correct
22 Correct 7 ms 5388 KB Output is correct
23 Correct 6 ms 5388 KB Output is correct
24 Correct 6 ms 5388 KB Output is correct
25 Correct 6 ms 5388 KB Output is correct
26 Correct 6 ms 5388 KB Output is correct
27 Correct 6 ms 5388 KB Output is correct
28 Correct 6 ms 5388 KB Output is correct
29 Correct 7 ms 5388 KB Output is correct
30 Correct 6 ms 5388 KB Output is correct
31 Correct 9 ms 5388 KB Output is correct
32 Correct 7 ms 5388 KB Output is correct
33 Incorrect 6 ms 5388 KB no wires in direction 1 between segments 8 and 10
34 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 7 ms 5224 KB Output is correct
3 Correct 6 ms 5224 KB Output is correct
4 Correct 7 ms 5324 KB Output is correct
5 Correct 7 ms 5388 KB Output is correct
6 Correct 7 ms 5388 KB Output is correct
7 Correct 7 ms 5388 KB Output is correct
8 Correct 7 ms 5388 KB Output is correct
9 Correct 7 ms 5388 KB Output is correct
10 Correct 7 ms 5388 KB Output is correct
11 Correct 9 ms 5388 KB Output is correct
12 Correct 8 ms 5388 KB Output is correct
13 Correct 7 ms 5388 KB Output is correct
14 Correct 7 ms 5388 KB Output is correct
15 Correct 7 ms 5388 KB Output is correct
16 Correct 5 ms 5388 KB Output is correct
17 Correct 5 ms 5388 KB Output is correct
18 Correct 8 ms 5388 KB Output is correct
19 Correct 6 ms 5388 KB Output is correct
20 Correct 6 ms 5388 KB Output is correct
21 Correct 7 ms 5388 KB Output is correct
22 Correct 7 ms 5388 KB Output is correct
23 Correct 6 ms 5388 KB Output is correct
24 Correct 6 ms 5388 KB Output is correct
25 Correct 6 ms 5388 KB Output is correct
26 Correct 6 ms 5388 KB Output is correct
27 Correct 6 ms 5388 KB Output is correct
28 Correct 6 ms 5388 KB Output is correct
29 Correct 7 ms 5388 KB Output is correct
30 Correct 6 ms 5388 KB Output is correct
31 Correct 9 ms 5388 KB Output is correct
32 Correct 7 ms 5388 KB Output is correct
33 Incorrect 6 ms 5388 KB no wires in direction 1 between segments 8 and 10
34 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 8084 KB Output is correct
2 Correct 82 ms 8084 KB Output is correct
3 Correct 75 ms 10616 KB Output is correct
4 Correct 114 ms 11644 KB Output is correct
5 Correct 288 ms 17804 KB Output is correct
6 Correct 151 ms 17804 KB Output is correct
7 Incorrect 293 ms 17932 KB no wires in direction 0 between segments 8545 and 8545
8 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5112 KB Output is correct
2 Correct 7 ms 5224 KB Output is correct
3 Correct 6 ms 5224 KB Output is correct
4 Correct 7 ms 5324 KB Output is correct
5 Correct 7 ms 5388 KB Output is correct
6 Correct 7 ms 5388 KB Output is correct
7 Correct 7 ms 5388 KB Output is correct
8 Correct 7 ms 5388 KB Output is correct
9 Correct 7 ms 5388 KB Output is correct
10 Correct 7 ms 5388 KB Output is correct
11 Correct 9 ms 5388 KB Output is correct
12 Correct 8 ms 5388 KB Output is correct
13 Correct 7 ms 5388 KB Output is correct
14 Correct 7 ms 5388 KB Output is correct
15 Correct 7 ms 5388 KB Output is correct
16 Correct 5 ms 5388 KB Output is correct
17 Correct 5 ms 5388 KB Output is correct
18 Correct 8 ms 5388 KB Output is correct
19 Correct 6 ms 5388 KB Output is correct
20 Correct 6 ms 5388 KB Output is correct
21 Correct 7 ms 5388 KB Output is correct
22 Correct 7 ms 5388 KB Output is correct
23 Correct 6 ms 5388 KB Output is correct
24 Correct 6 ms 5388 KB Output is correct
25 Correct 6 ms 5388 KB Output is correct
26 Correct 6 ms 5388 KB Output is correct
27 Correct 6 ms 5388 KB Output is correct
28 Correct 6 ms 5388 KB Output is correct
29 Correct 7 ms 5388 KB Output is correct
30 Correct 6 ms 5388 KB Output is correct
31 Correct 9 ms 5388 KB Output is correct
32 Correct 7 ms 5388 KB Output is correct
33 Incorrect 6 ms 5388 KB no wires in direction 1 between segments 8 and 10
34 Halted 0 ms 0 KB -