oj.uz

Submission #89395

# Submission time Handle Problem Language Result Execution time Memory
89395 2018-12-13T08:19:12 Z nicksona Nice sequence (IZhO18_sequence) C++14
58 / 100
 2000 ms 53152 KB 
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
int n,m;
int t;
bool OK=true;
int M=0;
vector <int> v[1000001];
int mas[1000001];
int fix[1000001];
void go (int u,int col,int sz){
	if (!OK) return ;
	fix[u]=col;
	for (int i=0;i<v[u].size();i++){
		int node=v[u][i];
		if (node>sz) break;
		if (fix[node]==col){
			OK=false;
			return ;
		}
		
		if (!OK) return ;	
		if (fix[node]==0) go(node,col,sz);
	}
}
inline bool check (int sz){
		
	OK=true;
	for (int i=0;i<=sz;i++){
		if (fix[i]==0){
			go(i,i+1,sz);
		}	
	}
	
	for (int i=0;i<=sz;i++){
		fix[i]=0;
	}
	
	return OK;
}

void top_sort (int u,int sz){
	fix[u]=1;
	for (int i=0;i<v[u].size();i++){
		int node=v[u][i];
		if (node>sz) break;
		if (fix[node]==0) top_sort(node,sz);
	}
	mas[u]=++M;
}

int nmas[1000001];
inline void solve (int sz){
	OK=true;
	for (int i=0;i<=sz;i++){
		if (fix[i]==0){
			top_sort(i,sz);
		}	
	}
	
	for (int i=0;i<=sz;i++){
		nmas[i]=mas[i]-mas[i-1];
		fix[i]=0;
	}
}
main () {
	ios::sync_with_stdio(false);
	cin>>t;

	while (t--){
		cin>>n>>m;
			
		int sz=400000;
		for (int i=0;i<=sz;i++){
			if (i+n<=sz){
				v[i].pb(i+n);
			}
			if (i+m<=sz){
				v[i+m].pb(i);
			}
		}
		
		for (int i=0;i<=sz;i++){
			sort (v[i].begin(),v[i].end());
		}
		
		int b=0,e=n+m,mid,ans=0;
		while (b<=e){
			mid= b + e >> 1;
			if (check(mid)){
				ans=mid;
				b=mid+1;
			}
			else{
				e=mid-1;
			}
		}
		M=0;
		if (ans>0) solve(ans);
		cout<<ans<<endl;
		for (int i=1;i<=ans;i++){
			cout<<nmas[i]<<" ";
		}
		
		cout<<endl;
		for (int i=0;i<=sz;i++){
			v[i].clear();
		}
		
	}
	return 0;
}
/*
1
2 4
  _   _   _          _
 | \ | | (_)        | |
 |  \| |  _    ___  | | __  ___    ___    _ __     __ _
 | . ` | | |  / __| | |/ / / __|  / _ \  | '_ \   / _` |
 | |\  | | | | (__  |   <  \__ \ | (_) | | | | | | (_| |
 |_| \_| |_|  \___| |_|\_\ |___/  \___/  |_| |_|  \__,_|

*/

Compilation message

sequence.cpp: In function 'void go(int, int, int)':
sequence.cpp:15:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<v[u].size();i++){
               ~^~~~~~~~~~~~
sequence.cpp: In function 'void top_sort(int, int)':
sequence.cpp:45:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0;i<v[u].size();i++){
               ~^~~~~~~~~~~~
sequence.cpp: At global scope:
sequence.cpp:67:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
sequence.cpp: In function 'int main()':
sequence.cpp:90:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
    mid= b + e >> 1;
         ~~^~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 36344 KB Ok
2 Correct 187 ms 36476 KB Ok
3 Correct 164 ms 36476 KB Ok
4 Correct 177 ms 36476 KB Ok
5 Correct 183 ms 36476 KB Ok
6 Correct 170 ms 36476 KB Ok
7 Correct 163 ms 36524 KB Ok
8 Correct 178 ms 36524 KB Ok
9 Correct 168 ms 36524 KB Ok
10 Correct 161 ms 36524 KB Ok
11 Correct 177 ms 36524 KB Ok
12 Correct 186 ms 36524 KB Ok

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 184 ms 36524 KB Ok
2 Correct 175 ms 36524 KB Ok
3 Correct 185 ms 36604 KB Ok
4 Correct 182 ms 36688 KB Ok
5 Correct 169 ms 36688 KB Ok
6 Correct 177 ms 36796 KB Ok
7 Correct 197 ms 37500 KB Ok
8 Correct 181 ms 37500 KB Ok
9 Correct 207 ms 37708 KB Ok
10 Correct 202 ms 37708 KB Ok

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 37708 KB Ok
2 Correct 171 ms 37708 KB Ok
3 Correct 165 ms 37708 KB Ok
4 Correct 190 ms 37708 KB Ok
5 Correct 174 ms 37708 KB Ok
6 Correct 172 ms 37708 KB Ok
7 Correct 161 ms 37708 KB Ok
8 Correct 169 ms 37708 KB Ok
9 Correct 175 ms 37708 KB Ok
10 Correct 175 ms 37708 KB Ok
11 Correct 166 ms 37708 KB Ok

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 37708 KB Ok
2 Correct 164 ms 37708 KB Ok
3 Correct 183 ms 37708 KB Ok
4 Correct 167 ms 37708 KB Ok
5 Correct 188 ms 37708 KB Ok
6 Correct 439 ms 49212 KB Ok
7 Correct 399 ms 50316 KB Ok
8 Correct 659 ms 53152 KB Ok
9 Correct 438 ms 53152 KB Ok
10 Correct 320 ms 53152 KB Ok
11 Correct 390 ms 53152 KB Ok

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 36344 KB Ok
2 Correct 187 ms 36476 KB Ok
3 Correct 164 ms 36476 KB Ok
4 Correct 177 ms 36476 KB Ok
5 Correct 183 ms 36476 KB Ok
6 Correct 170 ms 36476 KB Ok
7 Correct 163 ms 36524 KB Ok
8 Correct 178 ms 36524 KB Ok
9 Correct 168 ms 36524 KB Ok
10 Correct 161 ms 36524 KB Ok
11 Correct 177 ms 36524 KB Ok
12 Correct 186 ms 36524 KB Ok
13 Correct 97 ms 37708 KB Ok
14 Correct 171 ms 37708 KB Ok
15 Correct 165 ms 37708 KB Ok
16 Correct 190 ms 37708 KB Ok
17 Correct 174 ms 37708 KB Ok
18 Correct 172 ms 37708 KB Ok
19 Correct 161 ms 37708 KB Ok
20 Correct 169 ms 37708 KB Ok
21 Correct 175 ms 37708 KB Ok
22 Correct 175 ms 37708 KB Ok
23 Correct 166 ms 37708 KB Ok
24 Correct 199 ms 53152 KB Ok
25 Correct 202 ms 53152 KB Ok
26 Correct 184 ms 53152 KB Ok
27 Correct 185 ms 53152 KB Ok
28 Correct 206 ms 53152 KB Ok
29 Correct 183 ms 53152 KB Ok
30 Correct 187 ms 53152 KB Ok
31 Correct 189 ms 53152 KB Ok
32 Correct 201 ms 53152 KB Ok
33 Correct 204 ms 53152 KB Ok
34 Correct 198 ms 53152 KB Ok
35 Correct 198 ms 53152 KB Ok
36 Correct 211 ms 53152 KB Ok
37 Correct 196 ms 53152 KB Ok
38 Correct 216 ms 53152 KB Ok
39 Correct 193 ms 53152 KB Ok
40 Correct 217 ms 53152 KB Ok
41 Correct 184 ms 53152 KB Ok
42 Correct 189 ms 53152 KB Ok
43 Correct 189 ms 53152 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 36344 KB Ok
2 Correct 187 ms 36476 KB Ok
3 Correct 164 ms 36476 KB Ok
4 Correct 177 ms 36476 KB Ok
5 Correct 183 ms 36476 KB Ok
6 Correct 170 ms 36476 KB Ok
7 Correct 163 ms 36524 KB Ok
8 Correct 178 ms 36524 KB Ok
9 Correct 168 ms 36524 KB Ok
10 Correct 161 ms 36524 KB Ok
11 Correct 177 ms 36524 KB Ok
12 Correct 186 ms 36524 KB Ok
13 Correct 184 ms 36524 KB Ok
14 Correct 175 ms 36524 KB Ok
15 Correct 185 ms 36604 KB Ok
16 Correct 182 ms 36688 KB Ok
17 Correct 169 ms 36688 KB Ok
18 Correct 177 ms 36796 KB Ok
19 Correct 197 ms 37500 KB Ok
20 Correct 181 ms 37500 KB Ok
21 Correct 207 ms 37708 KB Ok
22 Correct 202 ms 37708 KB Ok
23 Correct 97 ms 37708 KB Ok
24 Correct 171 ms 37708 KB Ok
25 Correct 165 ms 37708 KB Ok
26 Correct 190 ms 37708 KB Ok
27 Correct 174 ms 37708 KB Ok
28 Correct 172 ms 37708 KB Ok
29 Correct 161 ms 37708 KB Ok
30 Correct 169 ms 37708 KB Ok
31 Correct 175 ms 37708 KB Ok
32 Correct 175 ms 37708 KB Ok
33 Correct 166 ms 37708 KB Ok
34 Correct 199 ms 53152 KB Ok
35 Correct 202 ms 53152 KB Ok
36 Correct 184 ms 53152 KB Ok
37 Correct 185 ms 53152 KB Ok
38 Correct 206 ms 53152 KB Ok
39 Correct 183 ms 53152 KB Ok
40 Correct 187 ms 53152 KB Ok
41 Correct 189 ms 53152 KB Ok
42 Correct 201 ms 53152 KB Ok
43 Correct 204 ms 53152 KB Ok
44 Correct 198 ms 53152 KB Ok
45 Correct 198 ms 53152 KB Ok
46 Correct 211 ms 53152 KB Ok
47 Correct 196 ms 53152 KB Ok
48 Correct 216 ms 53152 KB Ok
49 Correct 193 ms 53152 KB Ok
50 Correct 217 ms 53152 KB Ok
51 Correct 184 ms 53152 KB Ok
52 Correct 189 ms 53152 KB Ok
53 Correct 189 ms 53152 KB Ok
54 Correct 701 ms 53152 KB Ok
55 Correct 757 ms 53152 KB Ok
56 Correct 891 ms 53152 KB Ok
57 Correct 465 ms 53152 KB Ok
58 Correct 486 ms 53152 KB Ok
59 Correct 314 ms 53152 KB Ok
60 Correct 315 ms 53152 KB Ok
61 Correct 329 ms 53152 KB Ok
62 Correct 339 ms 53152 KB Ok
63 Correct 510 ms 53152 KB Ok
64 Correct 832 ms 53152 KB Ok
65 Correct 473 ms 53152 KB Ok
66 Correct 308 ms 53152 KB Ok
67 Correct 489 ms 53152 KB Ok
68 Correct 393 ms 53152 KB Ok
69 Correct 1749 ms 53152 KB Ok
70 Execution timed out 2051 ms 53152 KB Time limit exceeded
71 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 36344 KB Ok
2 Correct 187 ms 36476 KB Ok
3 Correct 164 ms 36476 KB Ok
4 Correct 177 ms 36476 KB Ok
5 Correct 183 ms 36476 KB Ok
6 Correct 170 ms 36476 KB Ok
7 Correct 163 ms 36524 KB Ok
8 Correct 178 ms 36524 KB Ok
9 Correct 168 ms 36524 KB Ok
10 Correct 161 ms 36524 KB Ok
11 Correct 177 ms 36524 KB Ok
12 Correct 186 ms 36524 KB Ok
13 Correct 184 ms 36524 KB Ok
14 Correct 175 ms 36524 KB Ok
15 Correct 185 ms 36604 KB Ok
16 Correct 182 ms 36688 KB Ok
17 Correct 169 ms 36688 KB Ok
18 Correct 177 ms 36796 KB Ok
19 Correct 197 ms 37500 KB Ok
20 Correct 181 ms 37500 KB Ok
21 Correct 207 ms 37708 KB Ok
22 Correct 202 ms 37708 KB Ok
23 Correct 97 ms 37708 KB Ok
24 Correct 171 ms 37708 KB Ok
25 Correct 165 ms 37708 KB Ok
26 Correct 190 ms 37708 KB Ok
27 Correct 174 ms 37708 KB Ok
28 Correct 172 ms 37708 KB Ok
29 Correct 161 ms 37708 KB Ok
30 Correct 169 ms 37708 KB Ok
31 Correct 175 ms 37708 KB Ok
32 Correct 175 ms 37708 KB Ok
33 Correct 166 ms 37708 KB Ok
34 Correct 189 ms 37708 KB Ok
35 Correct 164 ms 37708 KB Ok
36 Correct 183 ms 37708 KB Ok
37 Correct 167 ms 37708 KB Ok
38 Correct 188 ms 37708 KB Ok
39 Correct 439 ms 49212 KB Ok
40 Correct 399 ms 50316 KB Ok
41 Correct 659 ms 53152 KB Ok
42 Correct 438 ms 53152 KB Ok
43 Correct 320 ms 53152 KB Ok
44 Correct 390 ms 53152 KB Ok
45 Correct 199 ms 53152 KB Ok
46 Correct 202 ms 53152 KB Ok
47 Correct 184 ms 53152 KB Ok
48 Correct 185 ms 53152 KB Ok
49 Correct 206 ms 53152 KB Ok
50 Correct 183 ms 53152 KB Ok
51 Correct 187 ms 53152 KB Ok
52 Correct 189 ms 53152 KB Ok
53 Correct 201 ms 53152 KB Ok
54 Correct 204 ms 53152 KB Ok
55 Correct 198 ms 53152 KB Ok
56 Correct 198 ms 53152 KB Ok
57 Correct 211 ms 53152 KB Ok
58 Correct 196 ms 53152 KB Ok
59 Correct 216 ms 53152 KB Ok
60 Correct 193 ms 53152 KB Ok
61 Correct 217 ms 53152 KB Ok
62 Correct 184 ms 53152 KB Ok
63 Correct 189 ms 53152 KB Ok
64 Correct 189 ms 53152 KB Ok
65 Correct 701 ms 53152 KB Ok
66 Correct 757 ms 53152 KB Ok
67 Correct 891 ms 53152 KB Ok
68 Correct 465 ms 53152 KB Ok
69 Correct 486 ms 53152 KB Ok
70 Correct 314 ms 53152 KB Ok
71 Correct 315 ms 53152 KB Ok
72 Correct 329 ms 53152 KB Ok
73 Correct 339 ms 53152 KB Ok
74 Correct 510 ms 53152 KB Ok
75 Correct 832 ms 53152 KB Ok
76 Correct 473 ms 53152 KB Ok
77 Correct 308 ms 53152 KB Ok
78 Correct 489 ms 53152 KB Ok
79 Correct 393 ms 53152 KB Ok
80 Correct 1749 ms 53152 KB Ok
81 Execution timed out 2051 ms 53152 KB Time limit exceeded
82 Halted 0 ms 0 KB -