oj.uz

Submission #633729

# Submission time Handle Problem Language Result Execution time Memory
633729 2022-08-23T07:12:54 Z lovrot Nice sequence (IZhO18_sequence) C++11
34 / 100
 2000 ms 35788 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(){ 
	memset(bio, 0, sizeof(bio));
	memset(vis, 0, sizeof(vis));
	memset(cyc, 0, sizeof(cyc));
	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 18 ms 26708 KB Ok
2 Correct 21 ms 26740 KB Ok
3 Correct 21 ms 26628 KB Ok
4 Correct 21 ms 26756 KB Ok
5 Correct 21 ms 26684 KB Ok
6 Correct 21 ms 26708 KB Ok
7 Correct 20 ms 26760 KB Ok
8 Correct 20 ms 26708 KB Ok
9 Correct 21 ms 26708 KB Ok
10 Correct 21 ms 26708 KB Ok
11 Correct 22 ms 26700 KB Ok
12 Correct 20 ms 26704 KB Ok

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 26708 KB Ok
2 Correct 20 ms 26624 KB Ok
3 Correct 19 ms 26708 KB Ok
4 Correct 21 ms 26748 KB Ok
5 Correct 19 ms 26716 KB Ok
6 Correct 324 ms 26872 KB Ok
7 Execution timed out 2082 ms 27724 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 26668 KB Ok
2 Correct 17 ms 26624 KB Ok
3 Correct 18 ms 26708 KB Ok
4 Correct 18 ms 26708 KB Ok
5 Correct 19 ms 26756 KB Ok
6 Correct 19 ms 26628 KB Ok
7 Correct 20 ms 26632 KB Ok
8 Correct 19 ms 26708 KB Ok
9 Correct 18 ms 26624 KB Ok
10 Correct 19 ms 26756 KB Ok
11 Correct 20 ms 26764 KB Ok

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 26708 KB Ok
2 Correct 18 ms 26752 KB Ok
3 Correct 19 ms 26708 KB Ok
4 Correct 20 ms 26760 KB Ok
5 Correct 20 ms 26708 KB Ok
6 Execution timed out 2087 ms 35788 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 26708 KB Ok
2 Correct 21 ms 26740 KB Ok
3 Correct 21 ms 26628 KB Ok
4 Correct 21 ms 26756 KB Ok
5 Correct 21 ms 26684 KB Ok
6 Correct 21 ms 26708 KB Ok
7 Correct 20 ms 26760 KB Ok
8 Correct 20 ms 26708 KB Ok
9 Correct 21 ms 26708 KB Ok
10 Correct 21 ms 26708 KB Ok
11 Correct 22 ms 26700 KB Ok
12 Correct 20 ms 26704 KB Ok
13 Correct 15 ms 26668 KB Ok
14 Correct 17 ms 26624 KB Ok
15 Correct 18 ms 26708 KB Ok
16 Correct 18 ms 26708 KB Ok
17 Correct 19 ms 26756 KB Ok
18 Correct 19 ms 26628 KB Ok
19 Correct 20 ms 26632 KB Ok
20 Correct 19 ms 26708 KB Ok
21 Correct 18 ms 26624 KB Ok
22 Correct 19 ms 26756 KB Ok
23 Correct 20 ms 26764 KB Ok
24 Correct 29 ms 26908 KB Ok
25 Correct 30 ms 26808 KB Ok
26 Correct 30 ms 26868 KB Ok
27 Correct 31 ms 26852 KB Ok
28 Correct 27 ms 26836 KB Ok
29 Correct 29 ms 26892 KB Ok
30 Correct 27 ms 26836 KB Ok
31 Correct 28 ms 26908 KB Ok
32 Correct 30 ms 26880 KB Ok
33 Correct 31 ms 26896 KB Ok
34 Correct 59 ms 27152 KB Ok
35 Correct 70 ms 27144 KB Ok
36 Correct 140 ms 27340 KB Ok
37 Correct 71 ms 27124 KB Ok
38 Correct 72 ms 27180 KB Ok
39 Correct 55 ms 27064 KB Ok
40 Correct 78 ms 27144 KB Ok
41 Correct 74 ms 27124 KB Ok
42 Correct 64 ms 27100 KB Ok
43 Correct 75 ms 27188 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 26708 KB Ok
2 Correct 21 ms 26740 KB Ok
3 Correct 21 ms 26628 KB Ok
4 Correct 21 ms 26756 KB Ok
5 Correct 21 ms 26684 KB Ok
6 Correct 21 ms 26708 KB Ok
7 Correct 20 ms 26760 KB Ok
8 Correct 20 ms 26708 KB Ok
9 Correct 21 ms 26708 KB Ok
10 Correct 21 ms 26708 KB Ok
11 Correct 22 ms 26700 KB Ok
12 Correct 20 ms 26704 KB Ok
13 Correct 17 ms 26708 KB Ok
14 Correct 20 ms 26624 KB Ok
15 Correct 19 ms 26708 KB Ok
16 Correct 21 ms 26748 KB Ok
17 Correct 19 ms 26716 KB Ok
18 Correct 324 ms 26872 KB Ok
19 Execution timed out 2082 ms 27724 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 26708 KB Ok
2 Correct 21 ms 26740 KB Ok
3 Correct 21 ms 26628 KB Ok
4 Correct 21 ms 26756 KB Ok
5 Correct 21 ms 26684 KB Ok
6 Correct 21 ms 26708 KB Ok
7 Correct 20 ms 26760 KB Ok
8 Correct 20 ms 26708 KB Ok
9 Correct 21 ms 26708 KB Ok
10 Correct 21 ms 26708 KB Ok
11 Correct 22 ms 26700 KB Ok
12 Correct 20 ms 26704 KB Ok
13 Correct 17 ms 26708 KB Ok
14 Correct 20 ms 26624 KB Ok
15 Correct 19 ms 26708 KB Ok
16 Correct 21 ms 26748 KB Ok
17 Correct 19 ms 26716 KB Ok
18 Correct 324 ms 26872 KB Ok
19 Execution timed out 2082 ms 27724 KB Time limit exceeded
20 Halted 0 ms 0 KB -