oj.uz

Submission #742102

# Submission time Handle Problem Language Result Execution time Memory
742102 2023-05-15T15:27:36 Z onebit1024 Xylophone (JOI18_xylophone) C++17
0 / 100
 2 ms 208 KB 
#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;

// static int A[5000];
int pos = 1;
void get(int l, int r, int n){
	if(l>=r)return;
	int m = (l+r)/2;
	if(query(m,n)==(n-1)) pos = m,get(m+1,r,n);
	else  get(l,m-1,n);
}

void solve(int n) {

	vector<int>a(n+1);
	get(1,n,n);

	a[pos] = 1;
	if(pos > 1)a[pos-1] = 1+query(pos-1,pos);
	if(pos < n)a[pos+1] = 1+query(pos,pos+1);
	vector<int>taken(n+1);
	for(int i = pos-1;i<=pos+1;++i)taken[a[i]] = 1;
	for(int i = pos-2;i>=1;--i){
		set<int>opt;
		int c = query(i,i+1);
		if(a[i+1]-c >= 1 && !taken[a[i+1]-c])opt.insert(a[i+1]-c);
		if(a[i+1]+c <= n && !taken[a[i+1]+c])opt.insert(a[i+1]+c);
		if(opt.size()==1){
			a[i] = *opt.begin();
			taken[a[i]] = 1;
			continue;
		}
		int v = abs(a[i+1]-a[i+2]);
		int w = query(i,i+2);
		if(w==v){
			// a[i] lies between a[i+1] and a[i-1]
			for(auto x : opt){
				if(x >= min(a[i+1],a[i+2]) && x<= max(a[i+1],a[i+2])){
					a[i] = x;
					taken[x] = 1;
					continue;
				}
			}
		}else{
			for(auto x : opt){
				set<int>kk = {a[i+1],a[i+2],x};
				if((*--kk.end())-*kk.begin() == w){
					a[i] = x;
					taken[x] = 1;
					continue;
				}
			}
		}
	}
	for(int i = pos+2;i<=n;++i){
		set<int>opt;
		int c = query(i-1,i);
		if(a[i-1]-c >= 1 && !taken[a[i-1]-c])opt.insert(a[i-1]-c);
		if(a[i-1]+c <= n && !taken[a[i-1]+c])opt.insert(a[i-1]+c);
		if(opt.size()==1){
			a[i] = *opt.begin();
			taken[a[i]] = 1;
			continue;
		}
		int v = abs(a[i-1]-a[i-2]);
		int w = query(i-2,i);
		if(w==v){
			// a[i] lies between a[i-1] and a[i-2]
			for(auto x : opt){
				if(x >= min(a[i-1],a[i-2]) && x<= max(a[i-1],a[i-2])){
					a[i] = x;
					taken[x] = 1;
					continue;
				}
			}
		}else{
			for(auto x : opt){
				set<int>kk = {a[i-1],a[i-2],x};
				if((*--kk.end())-*kk.begin() == w){
					a[i] = x;
					taken[x] = 1;
					continue;
				}
			}
		}
	}	
	for(int i = 1;i<=n;++i){
		answer(i,a[i]);
	}
}

Subtask #1
0 / 11.0

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

Subtask #2
0 / 36.0

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

Subtask #3
0 / 53.0

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