oj.uz

Submission #633822

# Submission time Handle Problem Language Result Execution time Memory
633822 2022-08-23T09:29:06 Z lovrot Nice sequence (IZhO18_sequence) C++11
34 / 100
 2000 ms 13652 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 = N - 1, g[N][2];
int stk[N], pos;
bool cyc[N], bio[N], ts[N];

int stackTop(){ 
	return stk[pos];
}

void stackPop(){ 
	pos--;
}

void stackPush(int x){ 
	pos++;
	stk[pos] = x;
}

void pocisti(){ 
	pos = -1;
	for(int i = 0; i <= lastx; i++){ 
	 	g[i][0] = -1;
	 	g[i][1] = -1;
	 	bio[i] = cyc[i] = ts[i] = false;
	}
}

bool cycp(int u){
	bio[u] = true;
	cyc[u] = true;
	// cout << u << "\n";
	if(g[u][0] != -1){
		if(cyc[g[u][0]]){ 
			return true;
		}
		if(cycp(g[u][0])){ 
			return true;	
		}
	}
	if(g[u][1] != -1){
		if(cyc[g[u][1]]){ 
			return true;
		}
		if(cycp(g[u][1])){ 
			return true;	
		}
	}
	cyc[u] = false;
	return false;
}

void topSort(int u){ 
	ts[u] = true;
	if(g[u][0] != -1 && !ts[g[u][0]]){ 
		topSort(g[u][0]);
	}
	if(g[u][1] != -1 && !ts[g[u][1]]){ 
		topSort(g[u][1]);
	}
	stackPush(u);
}

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

	int val = ans;
	while(pos > -1){ 
		p[stackTop()] = val--;
		stackPop(); 
	}


	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][0] = i - m;
		}
		if(i - n >= 0){
			g[i - n][1] = i;
		}
	}

	//for(int i = 0; i <= x; i++) cout << bio[i] << " " << cyc[i] << " " << ts[i] << " | " << g[i][0] << " " << g[i][1] << "\n";
	for(int i = 0; i <= x; i++){ 
		if(bio[i] == 0){
			 // cout << i << " " << g[i][0] << " " << g[i][1] << " c\n";
			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 7 ms 11092 KB Ok
2 Correct 6 ms 11092 KB Ok
3 Correct 8 ms 11076 KB Ok
4 Correct 7 ms 10996 KB Ok
5 Correct 8 ms 11092 KB Ok
6 Correct 5 ms 11092 KB Ok
7 Correct 6 ms 11092 KB Ok
8 Correct 8 ms 10976 KB Ok
9 Correct 6 ms 10996 KB Ok
10 Correct 8 ms 11068 KB Ok
11 Correct 8 ms 11092 KB Ok
12 Correct 8 ms 11092 KB Ok

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11092 KB Ok
2 Correct 5 ms 11092 KB Ok
3 Correct 5 ms 11092 KB Ok
4 Correct 6 ms 11092 KB Ok
5 Correct 6 ms 11072 KB Ok
6 Correct 239 ms 11172 KB Ok
7 Execution timed out 2060 ms 11600 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

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

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11092 KB Ok
2 Correct 6 ms 11092 KB Ok
3 Correct 6 ms 11092 KB Ok
4 Correct 6 ms 11092 KB Ok
5 Correct 5 ms 11092 KB Ok
6 Execution timed out 2050 ms 13652 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 11092 KB Ok
2 Correct 6 ms 11092 KB Ok
3 Correct 8 ms 11076 KB Ok
4 Correct 7 ms 10996 KB Ok
5 Correct 8 ms 11092 KB Ok
6 Correct 5 ms 11092 KB Ok
7 Correct 6 ms 11092 KB Ok
8 Correct 8 ms 10976 KB Ok
9 Correct 6 ms 10996 KB Ok
10 Correct 8 ms 11068 KB Ok
11 Correct 8 ms 11092 KB Ok
12 Correct 8 ms 11092 KB Ok
13 Correct 5 ms 11092 KB Ok
14 Correct 5 ms 11092 KB Ok
15 Correct 8 ms 10976 KB Ok
16 Correct 6 ms 11092 KB Ok
17 Correct 6 ms 11092 KB Ok
18 Correct 7 ms 10972 KB Ok
19 Correct 6 ms 11092 KB Ok
20 Correct 7 ms 11092 KB Ok
21 Correct 7 ms 11092 KB Ok
22 Correct 6 ms 11092 KB Ok
23 Correct 5 ms 11092 KB Ok
24 Correct 12 ms 11044 KB Ok
25 Correct 11 ms 11092 KB Ok
26 Correct 10 ms 11136 KB Ok
27 Correct 10 ms 11152 KB Ok
28 Correct 11 ms 11116 KB Ok
29 Correct 8 ms 11148 KB Ok
30 Correct 11 ms 11112 KB Ok
31 Correct 11 ms 11092 KB Ok
32 Correct 10 ms 11092 KB Ok
33 Correct 12 ms 11136 KB Ok
34 Correct 34 ms 11296 KB Ok
35 Correct 45 ms 11316 KB Ok
36 Correct 93 ms 11372 KB Ok
37 Correct 39 ms 11360 KB Ok
38 Correct 43 ms 11376 KB Ok
39 Correct 27 ms 11316 KB Ok
40 Correct 53 ms 11372 KB Ok
41 Correct 43 ms 11280 KB Ok
42 Correct 44 ms 11348 KB Ok
43 Correct 43 ms 11352 KB Ok

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 11092 KB Ok
2 Correct 6 ms 11092 KB Ok
3 Correct 8 ms 11076 KB Ok
4 Correct 7 ms 10996 KB Ok
5 Correct 8 ms 11092 KB Ok
6 Correct 5 ms 11092 KB Ok
7 Correct 6 ms 11092 KB Ok
8 Correct 8 ms 10976 KB Ok
9 Correct 6 ms 10996 KB Ok
10 Correct 8 ms 11068 KB Ok
11 Correct 8 ms 11092 KB Ok
12 Correct 8 ms 11092 KB Ok
13 Correct 5 ms 11092 KB Ok
14 Correct 5 ms 11092 KB Ok
15 Correct 5 ms 11092 KB Ok
16 Correct 6 ms 11092 KB Ok
17 Correct 6 ms 11072 KB Ok
18 Correct 239 ms 11172 KB Ok
19 Execution timed out 2060 ms 11600 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 11092 KB Ok
2 Correct 6 ms 11092 KB Ok
3 Correct 8 ms 11076 KB Ok
4 Correct 7 ms 10996 KB Ok
5 Correct 8 ms 11092 KB Ok
6 Correct 5 ms 11092 KB Ok
7 Correct 6 ms 11092 KB Ok
8 Correct 8 ms 10976 KB Ok
9 Correct 6 ms 10996 KB Ok
10 Correct 8 ms 11068 KB Ok
11 Correct 8 ms 11092 KB Ok
12 Correct 8 ms 11092 KB Ok
13 Correct 5 ms 11092 KB Ok
14 Correct 5 ms 11092 KB Ok
15 Correct 5 ms 11092 KB Ok
16 Correct 6 ms 11092 KB Ok
17 Correct 6 ms 11072 KB Ok
18 Correct 239 ms 11172 KB Ok
19 Execution timed out 2060 ms 11600 KB Time limit exceeded
20 Halted 0 ms 0 KB -