oj.uz

Submission #881935

# Submission time Handle Problem Language Result Execution time Memory
881935 2023-12-02T09:54:40 Z Alan Xylophone (JOI18_xylophone) C++17
0 / 100
 1 ms 432 KB 
#include <bits/stdc++.h>
using namespace std;

int query(int s, int t);
void answer(int i, int a);

void solve(int N) {
	vector<int> ans (N+1);
	vector<bool> used (N+1);
	int l = 1, r = N+1;
	while (l+1 < r) {
		int mid = (l+r)/2;
		if (query(mid, N) == N-1) l = mid;
		else r = mid;
	}
	ans[l] = 1;
	if (l > 1) {
		ans[l-1] = ans[l] + query(l-1, l);
		used[ans[l-1]] = true;
	}
	if (l < N) {
		ans[l+1] = ans[l] + query(l, l+1);
		used[ans[l+1]] = true;
	}
	used[1] = true;
	for (int i = l-2; i > 0; i--) {
		int q = query(i, i+1);
		if (ans[i+1] + q > N || used[ans[i+1] + q]) ans[i] = ans[i+1] - q;
		else if (ans[i+1] - q < 1 || used[ans[i+1] - q]) ans[i] = ans[i+1] + q;
		else {
			int q2 = query(i, i+2);
			if (q2 == abs(ans[i+1] - ans[i+2])) ans[i] = ans[i+1] - q;
			else ans[i] = ans[i+1] + q;
		}
		used[ans[i]] = true;
	}
	for (int i = l+2; i <= N; i++) {
		int q = query(i-1, i);
		if (ans[i-1] + q > N || used[ans[i-1] + q]) ans[i] = ans[i-1] - q;
		else if (ans[i-1] - q < 1 || used[ans[i-1] - q]) ans[i] = ans[i-1] + q;
		else {
			int q2 = query(i-2, i);
			if (q2 == abs(ans[i-1] - ans[i-2])) ans[i] = ans[i-1] - q;
			else ans[i] = ans[i-1] + q;
		}
		used[ans[i]] = true;
	}
	for (int i = 1; i <= N; i++) answer(i, ans[i]);
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 1 ms 432 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 1 ms 432 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Runtime error 1 ms 432 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -