oj.uz

Submission #89388

# Submission time Handle Problem Language Result Execution time Memory
89388 2018-12-13T07:34:59 Z nicksona Nice sequence (IZhO18_sequence) C++14
34 / 100
 2000 ms 8444 KB 
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
using namespace std;
int n,m;
int t;
vector <int> v[100001];
bool OK=true;
int fix[100001];
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 4 ms 2680 KB Ok
2 Correct 5 ms 2816 KB Ok
3 Correct 5 ms 2868 KB Ok
4 Correct 4 ms 2868 KB Ok
5 Correct 4 ms 2868 KB Ok
6 Correct 4 ms 2932 KB Ok
7 Correct 4 ms 2932 KB Ok
8 Correct 4 ms 3056 KB Ok
9 Correct 4 ms 3116 KB Ok
10 Correct 4 ms 3116 KB Ok
11 Correct 4 ms 3116 KB Ok
12 Correct 5 ms 3116 KB Ok

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3116 KB Ok
2 Correct 4 ms 3116 KB Ok
3 Correct 4 ms 3116 KB Ok
4 Correct 4 ms 3116 KB Ok
5 Correct 4 ms 3116 KB Ok
6 Correct 442 ms 3472 KB Ok
7 Execution timed out 2060 ms 4116 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

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

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4116 KB Ok
2 Correct 4 ms 4116 KB Ok
3 Correct 4 ms 4116 KB Ok
4 Correct 4 ms 4116 KB Ok
5 Correct 4 ms 4116 KB Ok
6 Runtime error 12 ms 8444 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Ok
2 Correct 5 ms 2816 KB Ok
3 Correct 5 ms 2868 KB Ok
4 Correct 4 ms 2868 KB Ok
5 Correct 4 ms 2868 KB Ok
6 Correct 4 ms 2932 KB Ok
7 Correct 4 ms 2932 KB Ok
8 Correct 4 ms 3056 KB Ok
9 Correct 4 ms 3116 KB Ok
10 Correct 4 ms 3116 KB Ok
11 Correct 4 ms 3116 KB Ok
12 Correct 5 ms 3116 KB Ok
13 Correct 3 ms 4116 KB Ok
14 Correct 4 ms 4116 KB Ok
15 Correct 4 ms 4116 KB Ok
16 Correct 4 ms 4116 KB Ok
17 Correct 4 ms 4116 KB Ok
18 Correct 4 ms 4116 KB Ok
19 Correct 5 ms 4116 KB Ok
20 Correct 4 ms 4116 KB Ok
21 Correct 4 ms 4116 KB Ok
22 Correct 4 ms 4116 KB Ok
23 Correct 5 ms 4116 KB Ok
24 Correct 10 ms 8444 KB Ok
25 Correct 10 ms 8444 KB Ok
26 Correct 11 ms 8444 KB Ok
27 Correct 11 ms 8444 KB Ok
28 Correct 9 ms 8444 KB Ok
29 Correct 8 ms 8444 KB Ok
30 Correct 9 ms 8444 KB Ok
31 Correct 9 ms 8444 KB Ok
32 Correct 10 ms 8444 KB Ok
33 Correct 12 ms 8444 KB Ok
34 Correct 53 ms 8444 KB Ok
35 Correct 74 ms 8444 KB Ok
36 Correct 190 ms 8444 KB Ok
37 Correct 65 ms 8444 KB Ok
38 Correct 86 ms 8444 KB Ok
39 Correct 50 ms 8444 KB Ok
40 Correct 78 ms 8444 KB Ok
41 Correct 75 ms 8444 KB Ok
42 Correct 68 ms 8444 KB Ok
43 Correct 72 ms 8444 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Ok
2 Correct 5 ms 2816 KB Ok
3 Correct 5 ms 2868 KB Ok
4 Correct 4 ms 2868 KB Ok
5 Correct 4 ms 2868 KB Ok
6 Correct 4 ms 2932 KB Ok
7 Correct 4 ms 2932 KB Ok
8 Correct 4 ms 3056 KB Ok
9 Correct 4 ms 3116 KB Ok
10 Correct 4 ms 3116 KB Ok
11 Correct 4 ms 3116 KB Ok
12 Correct 5 ms 3116 KB Ok
13 Correct 4 ms 3116 KB Ok
14 Correct 4 ms 3116 KB Ok
15 Correct 4 ms 3116 KB Ok
16 Correct 4 ms 3116 KB Ok
17 Correct 4 ms 3116 KB Ok
18 Correct 442 ms 3472 KB Ok
19 Execution timed out 2060 ms 4116 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Ok
2 Correct 5 ms 2816 KB Ok
3 Correct 5 ms 2868 KB Ok
4 Correct 4 ms 2868 KB Ok
5 Correct 4 ms 2868 KB Ok
6 Correct 4 ms 2932 KB Ok
7 Correct 4 ms 2932 KB Ok
8 Correct 4 ms 3056 KB Ok
9 Correct 4 ms 3116 KB Ok
10 Correct 4 ms 3116 KB Ok
11 Correct 4 ms 3116 KB Ok
12 Correct 5 ms 3116 KB Ok
13 Correct 4 ms 3116 KB Ok
14 Correct 4 ms 3116 KB Ok
15 Correct 4 ms 3116 KB Ok
16 Correct 4 ms 3116 KB Ok
17 Correct 4 ms 3116 KB Ok
18 Correct 442 ms 3472 KB Ok
19 Execution timed out 2060 ms 4116 KB Time limit exceeded
20 Halted 0 ms 0 KB -