oj.uz

답안 #633872

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
633872 2022-08-23T10:44:17 Z lovrot Nice sequence (IZhO18_sequence) C++11
34 / 100
 2000 ms 5460 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 = 2 * 1e5 + 10;

int n, m, p[N], lastx = N - 1, g[N][2];
int stk[N], pos;
int cyc[N], bio[N], ts[N], cookie;

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

void stackPop(){ 
	pos--;
}

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

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

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

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

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

	cout << ans << "\n";
	for(int i = 1; i <= ans; i++) 
		cout << (p[i] - p[0]) - (p[i - 1] - p[0]) << " \n"[i == ans]; 
}

bool probaj(int x){ 
	pos = -1;
	cookie++;

	for(int i = 0; i <= x; i++){ 
		g[i][0] = g[i][1] = -1; 
		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 << i << ": " << g[i][0] << " " << g[i][1] << "\n";

	for(int i = 0; i <= x; i++){ 
		if(bio[i] != cookie){
			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;
}

Compilation message

sequence.cpp: In function 'void topSort(int)':
sequence.cpp:59:35: warning: logical not is only applied to the left hand side of comparison [-Wlogical-not-parentheses]
   59 |  if(g[u][1] != -1 && !ts[g[u][1]] != cookie){
      |                                   ^~
sequence.cpp:59:22: note: add parentheses around left hand side expression to silence this warning
   59 |  if(g[u][1] != -1 && !ts[g[u][1]] != cookie){
      |                      ^~~~~~~~~~~~
      |                      (           )

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 1 ms 340 KB Ok
3 Correct 1 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 340 KB Ok
6 Correct 1 ms 340 KB Ok
7 Correct 0 ms 340 KB Ok
8 Correct 0 ms 340 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 0 ms 340 KB Ok
11 Correct 0 ms 340 KB Ok
12 Correct 0 ms 340 KB Ok

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Ok
2 Correct 0 ms 340 KB Ok
3 Correct 0 ms 340 KB Ok
4 Correct 0 ms 340 KB Ok
5 Correct 1 ms 340 KB Ok
6 Correct 211 ms 460 KB Ok
7 Execution timed out 2069 ms 1024 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Ok
2 Correct 0 ms 340 KB Ok
3 Correct 0 ms 340 KB Ok
4 Correct 0 ms 340 KB Ok
5 Correct 0 ms 340 KB Ok
6 Correct 0 ms 340 KB Ok
7 Correct 1 ms 340 KB Ok
8 Correct 0 ms 340 KB Ok
9 Correct 0 ms 340 KB Ok
10 Correct 0 ms 340 KB Ok
11 Correct 0 ms 340 KB Ok

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 0 ms 340 KB Ok
3 Correct 1 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 340 KB Ok
6 Execution timed out 2076 ms 5460 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 1 ms 340 KB Ok
3 Correct 1 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 340 KB Ok
6 Correct 1 ms 340 KB Ok
7 Correct 0 ms 340 KB Ok
8 Correct 0 ms 340 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 0 ms 340 KB Ok
11 Correct 0 ms 340 KB Ok
12 Correct 0 ms 340 KB Ok
13 Correct 0 ms 340 KB Ok
14 Correct 0 ms 340 KB Ok
15 Correct 0 ms 340 KB Ok
16 Correct 0 ms 340 KB Ok
17 Correct 0 ms 340 KB Ok
18 Correct 0 ms 340 KB Ok
19 Correct 1 ms 340 KB Ok
20 Correct 0 ms 340 KB Ok
21 Correct 0 ms 340 KB Ok
22 Correct 0 ms 340 KB Ok
23 Correct 0 ms 340 KB Ok
24 Correct 4 ms 468 KB Ok
25 Correct 6 ms 468 KB Ok
26 Correct 4 ms 468 KB Ok
27 Correct 4 ms 468 KB Ok
28 Correct 3 ms 340 KB Ok
29 Correct 3 ms 396 KB Ok
30 Correct 3 ms 356 KB Ok
31 Correct 3 ms 468 KB Ok
32 Correct 3 ms 468 KB Ok
33 Correct 5 ms 452 KB Ok
34 Correct 27 ms 596 KB Ok
35 Correct 34 ms 704 KB Ok
36 Correct 79 ms 724 KB Ok
37 Correct 33 ms 700 KB Ok
38 Correct 37 ms 724 KB Ok
39 Correct 25 ms 632 KB Ok
40 Correct 40 ms 716 KB Ok
41 Correct 34 ms 640 KB Ok
42 Correct 30 ms 660 KB Ok
43 Correct 34 ms 732 KB Ok

Subtask #6
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 1 ms 340 KB Ok
3 Correct 1 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 340 KB Ok
6 Correct 1 ms 340 KB Ok
7 Correct 0 ms 340 KB Ok
8 Correct 0 ms 340 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 0 ms 340 KB Ok
11 Correct 0 ms 340 KB Ok
12 Correct 0 ms 340 KB Ok
13 Correct 0 ms 340 KB Ok
14 Correct 0 ms 340 KB Ok
15 Correct 0 ms 340 KB Ok
16 Correct 0 ms 340 KB Ok
17 Correct 1 ms 340 KB Ok
18 Correct 211 ms 460 KB Ok
19 Execution timed out 2069 ms 1024 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Ok
2 Correct 1 ms 340 KB Ok
3 Correct 1 ms 340 KB Ok
4 Correct 1 ms 340 KB Ok
5 Correct 1 ms 340 KB Ok
6 Correct 1 ms 340 KB Ok
7 Correct 0 ms 340 KB Ok
8 Correct 0 ms 340 KB Ok
9 Correct 1 ms 340 KB Ok
10 Correct 0 ms 340 KB Ok
11 Correct 0 ms 340 KB Ok
12 Correct 0 ms 340 KB Ok
13 Correct 0 ms 340 KB Ok
14 Correct 0 ms 340 KB Ok
15 Correct 0 ms 340 KB Ok
16 Correct 0 ms 340 KB Ok
17 Correct 1 ms 340 KB Ok
18 Correct 211 ms 460 KB Ok
19 Execution timed out 2069 ms 1024 KB Time limit exceeded
20 Halted 0 ms 0 KB -