oj.uz

Submission #89389

# Submission time Handle Problem Language Result Execution time Memory
89389 2018-12-13T07:38:53 Z nicksona Nice sequence (IZhO18_sequence) C++14
34 / 100
 2000 ms 9104 KB 
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
int n,m;
int t;
vector <int> v[200001];
bool OK=true;
int fix[200001];
void go (int u,int col){
	fix[u]=col;
	//cout<<u<<" "<<col<<endl;
	for (int i=0;i<v[u].size();i++){
		int node=v[u][i];
		if (fix[node]==col){
			OK=false;
			return ;
		}
		if (OK) go(node,col);
	}
}
bool check (int sz){
	
	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);
		}
	}
	
	OK=true;
	for (int i=0;i<=sz;i++){
		if (fix[i]==0){
			go(i,i+1);
		}	
	}
	
	for (int i=0;i<=sz;i++){
		fix[i]=0;
		v[i].clear();
	}
	//cout<<sz<<" "<<OK<<endl;
	return OK;
}
int M=0;
int mas[1000001];

void top_sort (int u,int col){
	fix[u]=col;
	for (int i=0;i<v[u].size();i++){
		int node=v[u][i];
		top_sort(node,col);
	}
	mas[u]=++M;
}
int nmas[1000001];
void solve (int sz){
	
	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);
		}
	}
	
	OK=true;
	for (int i=0;i<=sz;i++){
		if (fix[i]==0){
			top_sort(i,i+1);
		}	
	}
	
	
	for (int i=0;i<=sz;i++){
		nmas[i]=mas[i]-mas[i-1];
	}
	
	for (int i=0;i<=sz;i++){
		fix[i]=0;
		v[i].clear();
	}
}
main () {
	ios::sync_with_stdio(false);
	cin>>t;
	while (t--){
		cin>>n>>m;
		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;
	}
	return 0;
}
/*
  _   _   _          _
 | \ | | (_)        | |
 |  \| |  _    ___  | | __  ___    ___    _ __     __ _
 | . ` | | |  / __| | |/ / / __|  / _ \  | '_ \   / _` |
 | |\  | | | | (__  |   <  \__ \ | (_) | | | | | | (_| |
 |_| \_| |_|  \___| |_|\_\ |___/  \___/  |_| |_|  \__,_|

*/

Compilation message

sequence.cpp: In function 'void go(int, int)':
sequence.cpp:13: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:52: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:87:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^
sequence.cpp: In function 'int main()':
sequence.cpp:94: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 7 ms 5116 KB Ok
2 Correct 7 ms 5224 KB Ok
3 Correct 6 ms 5320 KB Ok
4 Correct 7 ms 5320 KB Ok
5 Correct 7 ms 5340 KB Ok
6 Correct 6 ms 5340 KB Ok
7 Correct 6 ms 5340 KB Ok
8 Correct 6 ms 5340 KB Ok
9 Correct 6 ms 5340 KB Ok
10 Correct 7 ms 5340 KB Ok
11 Correct 7 ms 5340 KB Ok
12 Correct 7 ms 5340 KB Ok

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5340 KB Ok
2 Correct 6 ms 5340 KB Ok
3 Correct 6 ms 5340 KB Ok
4 Correct 7 ms 5340 KB Ok
5 Correct 6 ms 5340 KB Ok
6 Correct 371 ms 5620 KB Ok
7 Execution timed out 2051 ms 6268 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6268 KB Ok
2 Correct 6 ms 6268 KB Ok
3 Correct 7 ms 6268 KB Ok
4 Correct 6 ms 6268 KB Ok
5 Correct 6 ms 6268 KB Ok
6 Correct 6 ms 6268 KB Ok
7 Correct 6 ms 6268 KB Ok
8 Correct 6 ms 6268 KB Ok
9 Correct 6 ms 6268 KB Ok
10 Correct 6 ms 6268 KB Ok
11 Correct 6 ms 6268 KB Ok

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 6268 KB Ok
2 Correct 7 ms 6268 KB Ok
3 Correct 7 ms 6268 KB Ok
4 Correct 7 ms 6268 KB Ok
5 Correct 7 ms 6268 KB Ok
6 Execution timed out 2058 ms 9104 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5116 KB Ok
2 Correct 7 ms 5224 KB Ok
3 Correct 6 ms 5320 KB Ok
4 Correct 7 ms 5320 KB Ok
5 Correct 7 ms 5340 KB Ok
6 Correct 6 ms 5340 KB Ok
7 Correct 6 ms 5340 KB Ok
8 Correct 6 ms 5340 KB Ok
9 Correct 6 ms 5340 KB Ok
10 Correct 7 ms 5340 KB Ok
11 Correct 7 ms 5340 KB Ok
12 Correct 7 ms 5340 KB Ok
13 Correct 6 ms 6268 KB Ok
14 Correct 6 ms 6268 KB Ok
15 Correct 7 ms 6268 KB Ok
16 Correct 6 ms 6268 KB Ok
17 Correct 6 ms 6268 KB Ok
18 Correct 6 ms 6268 KB Ok
19 Correct 6 ms 6268 KB Ok
20 Correct 6 ms 6268 KB Ok
21 Correct 6 ms 6268 KB Ok
22 Correct 6 ms 6268 KB Ok
23 Correct 6 ms 6268 KB Ok
24 Correct 13 ms 9104 KB Ok
25 Correct 13 ms 9104 KB Ok
26 Correct 13 ms 9104 KB Ok
27 Correct 13 ms 9104 KB Ok
28 Correct 11 ms 9104 KB Ok
29 Correct 11 ms 9104 KB Ok
30 Correct 11 ms 9104 KB Ok
31 Correct 12 ms 9104 KB Ok
32 Correct 13 ms 9104 KB Ok
33 Correct 14 ms 9104 KB Ok
34 Correct 57 ms 9104 KB Ok
35 Correct 80 ms 9104 KB Ok
36 Correct 198 ms 9104 KB Ok
37 Correct 65 ms 9104 KB Ok
38 Correct 75 ms 9104 KB Ok
39 Correct 46 ms 9104 KB Ok
40 Correct 74 ms 9104 KB Ok
41 Correct 67 ms 9104 KB Ok
42 Correct 64 ms 9104 KB Ok
43 Correct 64 ms 9104 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5116 KB Ok
2 Correct 7 ms 5224 KB Ok
3 Correct 6 ms 5320 KB Ok
4 Correct 7 ms 5320 KB Ok
5 Correct 7 ms 5340 KB Ok
6 Correct 6 ms 5340 KB Ok
7 Correct 6 ms 5340 KB Ok
8 Correct 6 ms 5340 KB Ok
9 Correct 6 ms 5340 KB Ok
10 Correct 7 ms 5340 KB Ok
11 Correct 7 ms 5340 KB Ok
12 Correct 7 ms 5340 KB Ok
13 Correct 6 ms 5340 KB Ok
14 Correct 6 ms 5340 KB Ok
15 Correct 6 ms 5340 KB Ok
16 Correct 7 ms 5340 KB Ok
17 Correct 6 ms 5340 KB Ok
18 Correct 371 ms 5620 KB Ok
19 Execution timed out 2051 ms 6268 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 5116 KB Ok
2 Correct 7 ms 5224 KB Ok
3 Correct 6 ms 5320 KB Ok
4 Correct 7 ms 5320 KB Ok
5 Correct 7 ms 5340 KB Ok
6 Correct 6 ms 5340 KB Ok
7 Correct 6 ms 5340 KB Ok
8 Correct 6 ms 5340 KB Ok
9 Correct 6 ms 5340 KB Ok
10 Correct 7 ms 5340 KB Ok
11 Correct 7 ms 5340 KB Ok
12 Correct 7 ms 5340 KB Ok
13 Correct 6 ms 5340 KB Ok
14 Correct 6 ms 5340 KB Ok
15 Correct 6 ms 5340 KB Ok
16 Correct 7 ms 5340 KB Ok
17 Correct 6 ms 5340 KB Ok
18 Correct 371 ms 5620 KB Ok
19 Execution timed out 2051 ms 6268 KB Time limit exceeded
20 Halted 0 ms 0 KB -