oj.uz

Submission #368345

# Submission time Handle Problem Language Result Execution time Memory
368345 2021-02-19T23:39:21 Z idontreallyknow Xylophone (JOI18_xylophone) C++14
0 / 100
 1 ms 364 KB 
#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
static int A[5000];

void solve(int N) {
	if (N == 1) {
		answer(1,1);
		return;
	}
	vector<int> dif1(N+1), dif2(N+1);
	for (int q = 2; q <= N; q++) {
		dif1[q] = query(q-1,q);
		if (q > 2) dif2[q] = query(q-2,q);
	}
	vector<bool> sgn(N+1);
	for (int q = 3; q <= N; q++) {
		if (dif2[q] == dif1[q]+dif1[q-1]) sgn[q] = sgn[q-1];
		else sgn[q] = !sgn[q-1];
	}
	vector<int> pref(N+1);
	for (int q = 2; q <= N; q++) {
		if (sgn[q]) pref[q] = pref[q-1]+dif1[q];
		else pref[q] = pref[q-1]-dif1[q];
	}
	set<pair<int,int>> seen;
	bool rev = false;
	int lo = -1, hi = -1;
	for(int q = 1; q <= N; q++) {
		if (seen.size()) {
			int x = pref[q] - seen.begin()->first;
			if (abs(x) == N-1) {
				lo = seen.begin()->second;
				hi = q;
				if (x < 0) rev = true;
				break;
			}
			x = pref[q] - seen.rbegin()->first;
			if (abs(x) == N-1) {
				lo = seen.rbegin()->second;
				hi = q;
				if (x < 0) rev = true;
				break;
			}
		}
		seen.insert(make_pair(pref[q],q));
	}
	if (rev) {
		for (int q = 2; q <= N; q++) sgn[q] = !sgn[q];
	}
	vector<int> ans(N+1);
	ans[1] = 1-pref[lo];
	for (int q = 2; q <= N; q++) {
		if (sgn[q]) ans[q] = ans[q-1]+dif1[q];
		else ans[q] = ans[q-1]-dif1[q];
	}
	for (int q = 1; q <= N; q++) {
		answer(q,ans[q]);
	}
}

Compilation message

xylophone.cpp: In function 'void solve(int)':
xylophone.cpp:28:15: warning: variable 'hi' set but not used [-Wunused-but-set-variable]
   28 |  int lo = -1, hi = -1;
      |               ^~
xylophone.cpp: At global scope:
xylophone.cpp:4:12: warning: 'A' defined but not used [-Wunused-variable]
    4 | static int A[5000];
      |            ^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Wrong Answer [4]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Wrong Answer [4]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Incorrect 1 ms 364 KB Wrong Answer [4]
4 Halted 0 ms 0 KB -