oj.uz

Submission #633732

# Submission time Handle Problem Language Result Execution time Memory
633732 2022-08-23T07:14:54 Z lovrot Nice sequence (IZhO18_sequence) C++11
34 / 100
 2000 ms 33388 KB 
#include <bits/stdc++.h> 

#define pb push_back 
#define X first
#define Y second
#define pii pair<int, int>

using namespace std;

const int N = 1e6;

int n, m, p[N], lastx;
bool bio[N], vis[N], cyc[N];

vector<int> g[N];
stack<int> stk;

void pocisti(){ 
	for(int i = 0; i <= lastx; i++){ 
	 	g[i].clear();
	 	bio[i] = false;
	 	vis[i] = false;
	 	cyc[i] = false;
	}
}

bool cycp(int u){ 	
	bio[u] = true;
	cyc[u] = true;
	for(int v : g[u]){ 
		// cout << u << " -> " << v << " " << bio[v] << "\n"; 
		if(bio[v]){ 
			return true;
		}
		if(cycp(v)){ 
			return true;	
		}
	}
	bio[u] = false;
	return false;
}

void topSort(int u){ 
	vis[u] = true;
	for(int v : g[u]){ 
		if(vis[v]) continue;
		topSort(v);
	}
	stk.push(u);
}

void output(int ans){ 
	for(int i = 0; i <= ans; i++)
		if(!vis[i]) topSort(i);

	int cnt = ans;
	while(!stk.empty()){ 
		p[stk.top()] = cnt--;
		stk.pop(); 
	}


	for(int i = ans; i >= 0; i--){
		p[i] -= p[0];
	}
	for(int i = 0; i <= ans; i++){ 
		if(i >= n && p[i] - p[i - n] >= 0){ 
			cout << -1 << "\n";
			return;
		}
		if(i >= m && p[i] - p[i - m] <= 0){ 
			cout << -1 << "\n";
			return;
		}	
		if(i > 0 && p[i] - p[i - 1] == 0){ 
			cout << -1 << "\n";
		}
	}
	cout << ans << "\n";
	for(int i = 1; i <= ans; i++) 
		cout << p[i] - p[i - 1] << " \n"[i == ans]; 
}

bool probaj(int x){ 
	pocisti();
	lastx = x;

	for(int i = 1; i <= x; i++){ 
		if(i - m >= 0){
			g[i].pb(i - m);
		}
		if(i - n >= 0){
			g[i - n].pb(i);
		}
	}
	
	for(int i = 0; i <= x; i++){ 
		if(!cyc[i]){
			if(cycp(i))
				return false;
		}
	}
	return true;
}

void task(){ 
	cin >> n >> m;

	int lo = 0, hi = 2 * (n + m) + 1;
	while(hi - lo > 1){ 
		int mi = (lo + hi) / 2;
		if(probaj(mi))
			lo = mi;
		else 
			hi = mi;
	}
	probaj(lo);
	output(lo);
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int t;	
	cin >> t;

	while(t--){ 
		task();
	}
	return 0;
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Ok
2 Correct 14 ms 23756 KB Ok
3 Correct 13 ms 23780 KB Ok
4 Correct 12 ms 23780 KB Ok
5 Correct 13 ms 23764 KB Ok
6 Correct 16 ms 23764 KB Ok
7 Correct 17 ms 23828 KB Ok
8 Correct 13 ms 23832 KB Ok
9 Correct 14 ms 23764 KB Ok
10 Correct 13 ms 23764 KB Ok
11 Correct 13 ms 23764 KB Ok
12 Correct 12 ms 23764 KB Ok

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23828 KB Ok
2 Correct 13 ms 23764 KB Ok
3 Correct 12 ms 23768 KB Ok
4 Correct 13 ms 23764 KB Ok
5 Correct 12 ms 23764 KB Ok
6 Correct 314 ms 24060 KB Ok
7 Execution timed out 2087 ms 24752 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB Ok
2 Correct 12 ms 23724 KB Ok
3 Correct 12 ms 23764 KB Ok
4 Correct 13 ms 23728 KB Ok
5 Correct 13 ms 23716 KB Ok
6 Correct 12 ms 23764 KB Ok
7 Correct 14 ms 23704 KB Ok
8 Correct 13 ms 23764 KB Ok
9 Correct 12 ms 23764 KB Ok
10 Correct 14 ms 23796 KB Ok
11 Correct 13 ms 23764 KB Ok

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23736 KB Ok
2 Correct 13 ms 23828 KB Ok
3 Correct 13 ms 23764 KB Ok
4 Correct 13 ms 23828 KB Ok
5 Correct 12 ms 23764 KB Ok
6 Execution timed out 2054 ms 33388 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Ok
2 Correct 14 ms 23756 KB Ok
3 Correct 13 ms 23780 KB Ok
4 Correct 12 ms 23780 KB Ok
5 Correct 13 ms 23764 KB Ok
6 Correct 16 ms 23764 KB Ok
7 Correct 17 ms 23828 KB Ok
8 Correct 13 ms 23832 KB Ok
9 Correct 14 ms 23764 KB Ok
10 Correct 13 ms 23764 KB Ok
11 Correct 13 ms 23764 KB Ok
12 Correct 12 ms 23764 KB Ok
13 Correct 12 ms 23764 KB Ok
14 Correct 12 ms 23724 KB Ok
15 Correct 12 ms 23764 KB Ok
16 Correct 13 ms 23728 KB Ok
17 Correct 13 ms 23716 KB Ok
18 Correct 12 ms 23764 KB Ok
19 Correct 14 ms 23704 KB Ok
20 Correct 13 ms 23764 KB Ok
21 Correct 12 ms 23764 KB Ok
22 Correct 14 ms 23796 KB Ok
23 Correct 13 ms 23764 KB Ok
24 Correct 19 ms 23892 KB Ok
25 Correct 24 ms 24008 KB Ok
26 Correct 19 ms 23892 KB Ok
27 Correct 18 ms 24008 KB Ok
28 Correct 17 ms 23936 KB Ok
29 Correct 16 ms 23952 KB Ok
30 Correct 18 ms 23892 KB Ok
31 Correct 18 ms 23892 KB Ok
32 Correct 18 ms 23924 KB Ok
33 Correct 19 ms 23892 KB Ok
34 Correct 49 ms 24148 KB Ok
35 Correct 62 ms 24172 KB Ok
36 Correct 127 ms 24304 KB Ok
37 Correct 56 ms 24268 KB Ok
38 Correct 60 ms 24220 KB Ok
39 Correct 44 ms 24232 KB Ok
40 Correct 73 ms 24280 KB Ok
41 Correct 71 ms 24280 KB Ok
42 Correct 56 ms 24224 KB Ok
43 Correct 58 ms 24260 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Ok
2 Correct 14 ms 23756 KB Ok
3 Correct 13 ms 23780 KB Ok
4 Correct 12 ms 23780 KB Ok
5 Correct 13 ms 23764 KB Ok
6 Correct 16 ms 23764 KB Ok
7 Correct 17 ms 23828 KB Ok
8 Correct 13 ms 23832 KB Ok
9 Correct 14 ms 23764 KB Ok
10 Correct 13 ms 23764 KB Ok
11 Correct 13 ms 23764 KB Ok
12 Correct 12 ms 23764 KB Ok
13 Correct 12 ms 23828 KB Ok
14 Correct 13 ms 23764 KB Ok
15 Correct 12 ms 23768 KB Ok
16 Correct 13 ms 23764 KB Ok
17 Correct 12 ms 23764 KB Ok
18 Correct 314 ms 24060 KB Ok
19 Execution timed out 2087 ms 24752 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Ok
2 Correct 14 ms 23756 KB Ok
3 Correct 13 ms 23780 KB Ok
4 Correct 12 ms 23780 KB Ok
5 Correct 13 ms 23764 KB Ok
6 Correct 16 ms 23764 KB Ok
7 Correct 17 ms 23828 KB Ok
8 Correct 13 ms 23832 KB Ok
9 Correct 14 ms 23764 KB Ok
10 Correct 13 ms 23764 KB Ok
11 Correct 13 ms 23764 KB Ok
12 Correct 12 ms 23764 KB Ok
13 Correct 12 ms 23828 KB Ok
14 Correct 13 ms 23764 KB Ok
15 Correct 12 ms 23768 KB Ok
16 Correct 13 ms 23764 KB Ok
17 Correct 12 ms 23764 KB Ok
18 Correct 314 ms 24060 KB Ok
19 Execution timed out 2087 ms 24752 KB Time limit exceeded
20 Halted 0 ms 0 KB -