oj.uz

답안 #40505

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
40505 2018-02-03T08:27:25 Z szawinis Nice sequence (IZhO18_sequence) C++14
0 / 100
 35 ms 17400 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5+1;

int n, m, dsu[N], nxt[N], pos[N], res[N];
bool mark[N];

int root(int v) { return (dsu[v] < 0 ? v : dsu[v] = root(dsu[v])); }
void merge(int u, int v) {
	nxt[u] = v;
	mark[v] = true;
	u = root(u), v = root(v);
	assert(u != v);
	dsu[u] += dsu[v];
	dsu[v] = u;
}

void solve() {
	scanf("%d %d", &n, &m);
	fill(dsu, dsu+N, -1);
	fill(nxt, nxt+N, -1);
	fill(pos, pos+N, -1);
	fill(mark, mark+N, 0);
	fill(res, res+N, 0);
	int k = 0;
	for(k = 1; k <= 2*max(n, m); k++) {
		// cout << k - n << ' ' << k << ' ' << endl;
		// cout << k << ' ' << k - m << endl;

		if(k - n >= 0 && k - m >= 0) {
			if(root(k - n) == root(k - m) || root(k) == root(k - n) || root(k) == root(k - m)) break;
			merge(k - n, k);
			merge(k, k - m);
		} else if(k - n >= 0) {
			if(root(k) == root(k - n)) break;
			merge(k - n, k);
		} else if(k - m >= 0) {
			if(root(k) == root(k - m)) break;
			merge(k, k - m);
		}
	}
	--k;
	vector<int> ord;
	for(int i = 0; i <= k; i++) if(!mark[i]) {
		ord.push_back(i);
		break;
	}
	assert(!ord.empty());

	for(int i = ord[0]; nxt[i] != -1; i = nxt[i]) ord.push_back(nxt[i]);
	for(int i = 0; i <= k; i++) pos[ord[i]] = i;
	for(int i = 1; i <= k; i++) res[i] = pos[i-1] - pos[i];
	printf("%d\n", k);
	for(int i = 1; i <= k; i++) printf("%d ", res[i]);
	printf("\n");
}

int main() {
	int t;
	scanf("%d", &t);
	while(t--) solve();
}

Compilation message

sequence.cpp: In function 'void solve()':
sequence.cpp:19:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &m);
                        ^
sequence.cpp: In function 'int main()':
sequence.cpp:60:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &t);
                 ^

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 8568 KB Ok
2 Runtime error 35 ms 17248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 17248 KB there is incorrect sequence
2 Halted 0 ms 0 KB -

Subtask #3
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 17308 KB Ok
2 Correct 21 ms 17360 KB Ok
3 Incorrect 22 ms 17360 KB there is incorrect sequence
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 17400 KB there is incorrect sequence
2 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 8568 KB Ok
2 Runtime error 35 ms 17248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 8568 KB Ok
2 Runtime error 35 ms 17248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #7
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 8568 KB Ok
2 Runtime error 35 ms 17248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -