oj.uz

Submission #108438

# Submission time Handle Problem Language Result Execution time Memory
108438 2019-04-29T14:12:54 Z FiloSanza Xylophone (JOI18_xylophone) C++14
0 / 100
 3 ms 256 KB 
#include "xylophone.h"
#include <bits/stdc++.h>

using namespace std;

static int A[5000];

void solve(int N) {
	int lo = 1, hi = N-1;
	int mini, maxi;

	/*
	cout << "START";
	cout << endl;*/

	while(query(lo, hi) == N-1) hi--;
	maxi = hi+1;
	while(query(lo, maxi) == N-1) lo++;
	mini = lo-1;

	//solve
	vector<bool> found(N+1, false);
	vector<int> ans(N+1, -1);
	ans[mini] = 1;
	ans[maxi] = N;
	found[1] = found[N] = 1;

	answer(mini, 1);
	answer(maxi, N);

	/*
	cout << "MINI: " << mini << endl;
	cout << "MAXI: " << maxi << endl;
	cout.flush();*/

	queue<int> q;
	q.push(mini-1);
	q.push(mini+1);
	q.push(maxi-1);
	q.push(maxi+1);

	while(!q.empty()){
		int curr = q.front();
		q.pop();

		if(curr < 1 || curr > N) continue;
		if(ans[curr] >= 0) continue;

		int prec = ans[curr-1] != -1 ? curr-1 : curr+1;
		//cout << "CURR: " << curr << "\nPREC: " << prec << endl;
		int diff = query(min(curr, prec), max(curr, prec));
		
		if(ans[prec] + diff > N) ans[curr] = ans[prec] - diff;
		else if(ans[prec] - diff < 1) ans[curr] = ans[prec] + diff;
		else if(!found[ans[prec] - diff] && found[ans[prec] + diff]) ans[curr] = ans[prec] - diff;
		else if(found[ans[prec] - diff] && !found[ans[prec] + diff]) ans[curr] = ans[prec] + diff;
		else if(!found[ans[prec] - diff] && !found[ans[prec] + diff]){
		//	cout << "CURR: " << curr << "\nMINI: " << mini << endl;
			int d2 = query(min(curr, mini), max(curr, mini));
			if(d2 > diff) ans[curr] = ans[prec] + diff;
			else ans[curr] = ans[prec] - diff;
		}

		found[ans[curr]] = 1;
		//cout  << "POS-" << curr << ": " << ans[curr] << endl;
		answer(curr, ans[curr]);

		cout.flush();

		q.push(curr-1);
		q.push(curr+1);
	}
}

Compilation message

xylophone.cpp:6:12: warning: 'A' defined but not used [-Wunused-variable]
 static int A[5000];
            ^

Subtask #1
0 / 11.0

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

Subtask #2
0 / 36.0

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

Subtask #3
0 / 53.0

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