oj.uz

Submission #118054

# Submission time Handle Problem Language Result Execution time Memory
118054 2019-06-18T01:57:34 Z samjia2000 Alternating Current (BOI18_alternating) C++14
13 / 100
 3000 ms 11820 KB 
#include<bits/stdc++.h>

#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)

using namespace std;

typedef double db;
typedef long long LL;

int get(){
	char ch;
	while(ch=getchar(),(ch<'0'||ch>'9')&&ch!='-');
	if (ch=='-'){
		int s=0;
		while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
		return -s;
	}
	int s=ch-'0';
	while(ch=getchar(),ch>='0'&&ch<='9')s=s*10+ch-'0';
	return s;
}

const int N = 2e5+5;

int n,m;
struct section{
	int l,r,id;
	section(const int l_=0,const int r_=0){l=l_;r=r_;}
}s[N],a[N],b[N];
int ka,kb;

bool cmp(section a,section b){return a.l!=b.l?a.l<b.l:a.r>b.r;}

int ans[N];
bool yes;
int ad1[N],ad2[N];

void dfs(int x){
	if (x>m){
		fo(i,1,n)ad1[i]=ad2[i]=0;
		fo(i,1,m)
		if (ans[i]){
			ad1[s[i].l]++;
			if (s[i].r>=s[i].l)ad1[s[i].r+1]--;
			else ad1[1]++,ad1[s[i].r+1]--;
		}
		else{
			ad2[s[i].l]++;
			if (s[i].r>=s[i].l)ad2[s[i].r+1]--;
			else ad2[1]++,ad2[s[i].r+1]--;
		}
		fo(i,1,n)ad1[i]+=ad1[i-1],ad2[i]+=ad2[i-1];
		bool pd=1;
		fo(i,1,n)pd&=(ad1[i]>0&&ad2[i]>0);
		if (pd){
			yes=1;
			fo(i,1,m)printf("%d",ans[i]);
			return;
		}
		return;
	}
	ans[x]=0;
	dfs(x+1);
	if (yes)return;
	ans[x]=1;
	dfs(x+1);
}

int main(){
	n=get();m=get();
	int pm=m;
	fo(i,1,m){
		s[i].l=get();s[i].r=get();
		s[i].id=i;
	}
	dfs(1);
	if (!yes)printf("impossible\n");
	//else printf("possible\n");
	return 0;
}

Compilation message

alternating.cpp: In function 'int main()':
alternating.cpp:72:6: warning: unused variable 'pm' [-Wunused-variable]
  int pm=m;
      ^~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7424 KB Output is correct
2 Correct 7 ms 7424 KB Output is correct
3 Correct 7 ms 7424 KB Output is correct
4 Correct 7 ms 7424 KB Output is correct
5 Correct 7 ms 7424 KB Output is correct
6 Correct 7 ms 7424 KB Output is correct
7 Correct 7 ms 7424 KB Output is correct
8 Correct 8 ms 7424 KB Output is correct
9 Correct 8 ms 7424 KB Output is correct
10 Correct 8 ms 7424 KB Output is correct
11 Correct 8 ms 7424 KB Output is correct
12 Correct 7 ms 7424 KB Output is correct
13 Correct 8 ms 7424 KB Output is correct
14 Correct 7 ms 7424 KB Output is correct
15 Correct 9 ms 7424 KB Output is correct
16 Correct 7 ms 7424 KB Output is correct
17 Correct 7 ms 7424 KB Output is correct
18 Correct 8 ms 7424 KB Output is correct
19 Correct 7 ms 7424 KB Output is correct
20 Correct 7 ms 7424 KB Output is correct
21 Correct 7 ms 7424 KB Output is correct
22 Correct 9 ms 7424 KB Output is correct
23 Correct 8 ms 7424 KB Output is correct
24 Correct 7 ms 7552 KB Output is correct
25 Correct 7 ms 7424 KB Output is correct
26 Correct 7 ms 7424 KB Output is correct
27 Correct 7 ms 7424 KB Output is correct
28 Correct 7 ms 7424 KB Output is correct
29 Correct 7 ms 7424 KB Output is correct
30 Correct 8 ms 7424 KB Output is correct
31 Correct 7 ms 7424 KB Output is correct
32 Correct 7 ms 7424 KB Output is correct
33 Correct 7 ms 7424 KB Output is correct
34 Correct 8 ms 7424 KB Output is correct
35 Correct 12 ms 7424 KB Output is correct
36 Correct 7 ms 7424 KB Output is correct
37 Correct 7 ms 7424 KB Output is correct
38 Correct 11 ms 7424 KB Output is correct
39 Correct 8 ms 7424 KB Output is correct
40 Correct 7 ms 7424 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7424 KB Output is correct
2 Correct 7 ms 7424 KB Output is correct
3 Correct 7 ms 7424 KB Output is correct
4 Correct 7 ms 7424 KB Output is correct
5 Correct 7 ms 7424 KB Output is correct
6 Correct 7 ms 7424 KB Output is correct
7 Correct 7 ms 7424 KB Output is correct
8 Correct 8 ms 7424 KB Output is correct
9 Correct 8 ms 7424 KB Output is correct
10 Correct 8 ms 7424 KB Output is correct
11 Correct 8 ms 7424 KB Output is correct
12 Correct 7 ms 7424 KB Output is correct
13 Correct 8 ms 7424 KB Output is correct
14 Correct 7 ms 7424 KB Output is correct
15 Correct 9 ms 7424 KB Output is correct
16 Correct 7 ms 7424 KB Output is correct
17 Correct 7 ms 7424 KB Output is correct
18 Correct 8 ms 7424 KB Output is correct
19 Correct 7 ms 7424 KB Output is correct
20 Correct 7 ms 7424 KB Output is correct
21 Correct 7 ms 7424 KB Output is correct
22 Correct 9 ms 7424 KB Output is correct
23 Correct 8 ms 7424 KB Output is correct
24 Correct 7 ms 7552 KB Output is correct
25 Correct 7 ms 7424 KB Output is correct
26 Correct 7 ms 7424 KB Output is correct
27 Correct 7 ms 7424 KB Output is correct
28 Correct 7 ms 7424 KB Output is correct
29 Correct 7 ms 7424 KB Output is correct
30 Correct 8 ms 7424 KB Output is correct
31 Correct 7 ms 7424 KB Output is correct
32 Correct 7 ms 7424 KB Output is correct
33 Correct 7 ms 7424 KB Output is correct
34 Correct 8 ms 7424 KB Output is correct
35 Correct 12 ms 7424 KB Output is correct
36 Correct 7 ms 7424 KB Output is correct
37 Correct 7 ms 7424 KB Output is correct
38 Correct 11 ms 7424 KB Output is correct
39 Correct 8 ms 7424 KB Output is correct
40 Correct 7 ms 7424 KB Output is correct
41 Correct 7 ms 7424 KB Output is correct
42 Correct 9 ms 7424 KB Output is correct
43 Execution timed out 3029 ms 7424 KB Time limit exceeded
44 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7424 KB Output is correct
2 Correct 7 ms 7424 KB Output is correct
3 Correct 7 ms 7424 KB Output is correct
4 Correct 7 ms 7424 KB Output is correct
5 Correct 7 ms 7424 KB Output is correct
6 Correct 7 ms 7424 KB Output is correct
7 Correct 7 ms 7424 KB Output is correct
8 Correct 8 ms 7424 KB Output is correct
9 Correct 8 ms 7424 KB Output is correct
10 Correct 8 ms 7424 KB Output is correct
11 Correct 8 ms 7424 KB Output is correct
12 Correct 7 ms 7424 KB Output is correct
13 Correct 8 ms 7424 KB Output is correct
14 Correct 7 ms 7424 KB Output is correct
15 Correct 9 ms 7424 KB Output is correct
16 Correct 7 ms 7424 KB Output is correct
17 Correct 7 ms 7424 KB Output is correct
18 Correct 8 ms 7424 KB Output is correct
19 Correct 7 ms 7424 KB Output is correct
20 Correct 7 ms 7424 KB Output is correct
21 Correct 7 ms 7424 KB Output is correct
22 Correct 9 ms 7424 KB Output is correct
23 Correct 8 ms 7424 KB Output is correct
24 Correct 7 ms 7552 KB Output is correct
25 Correct 7 ms 7424 KB Output is correct
26 Correct 7 ms 7424 KB Output is correct
27 Correct 7 ms 7424 KB Output is correct
28 Correct 7 ms 7424 KB Output is correct
29 Correct 7 ms 7424 KB Output is correct
30 Correct 8 ms 7424 KB Output is correct
31 Correct 7 ms 7424 KB Output is correct
32 Correct 7 ms 7424 KB Output is correct
33 Correct 7 ms 7424 KB Output is correct
34 Correct 8 ms 7424 KB Output is correct
35 Correct 12 ms 7424 KB Output is correct
36 Correct 7 ms 7424 KB Output is correct
37 Correct 7 ms 7424 KB Output is correct
38 Correct 11 ms 7424 KB Output is correct
39 Correct 8 ms 7424 KB Output is correct
40 Correct 7 ms 7424 KB Output is correct
41 Correct 7 ms 7424 KB Output is correct
42 Correct 9 ms 7424 KB Output is correct
43 Execution timed out 3029 ms 7424 KB Time limit exceeded
44 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 11820 KB Output is correct
2 Correct 9 ms 8192 KB Output is correct
3 Execution timed out 3034 ms 9984 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 7424 KB Output is correct
2 Correct 7 ms 7424 KB Output is correct
3 Correct 7 ms 7424 KB Output is correct
4 Correct 7 ms 7424 KB Output is correct
5 Correct 7 ms 7424 KB Output is correct
6 Correct 7 ms 7424 KB Output is correct
7 Correct 7 ms 7424 KB Output is correct
8 Correct 8 ms 7424 KB Output is correct
9 Correct 8 ms 7424 KB Output is correct
10 Correct 8 ms 7424 KB Output is correct
11 Correct 8 ms 7424 KB Output is correct
12 Correct 7 ms 7424 KB Output is correct
13 Correct 8 ms 7424 KB Output is correct
14 Correct 7 ms 7424 KB Output is correct
15 Correct 9 ms 7424 KB Output is correct
16 Correct 7 ms 7424 KB Output is correct
17 Correct 7 ms 7424 KB Output is correct
18 Correct 8 ms 7424 KB Output is correct
19 Correct 7 ms 7424 KB Output is correct
20 Correct 7 ms 7424 KB Output is correct
21 Correct 7 ms 7424 KB Output is correct
22 Correct 9 ms 7424 KB Output is correct
23 Correct 8 ms 7424 KB Output is correct
24 Correct 7 ms 7552 KB Output is correct
25 Correct 7 ms 7424 KB Output is correct
26 Correct 7 ms 7424 KB Output is correct
27 Correct 7 ms 7424 KB Output is correct
28 Correct 7 ms 7424 KB Output is correct
29 Correct 7 ms 7424 KB Output is correct
30 Correct 8 ms 7424 KB Output is correct
31 Correct 7 ms 7424 KB Output is correct
32 Correct 7 ms 7424 KB Output is correct
33 Correct 7 ms 7424 KB Output is correct
34 Correct 8 ms 7424 KB Output is correct
35 Correct 12 ms 7424 KB Output is correct
36 Correct 7 ms 7424 KB Output is correct
37 Correct 7 ms 7424 KB Output is correct
38 Correct 11 ms 7424 KB Output is correct
39 Correct 8 ms 7424 KB Output is correct
40 Correct 7 ms 7424 KB Output is correct
41 Correct 7 ms 7424 KB Output is correct
42 Correct 9 ms 7424 KB Output is correct
43 Execution timed out 3029 ms 7424 KB Time limit exceeded
44 Halted 0 ms 0 KB -