이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
int A[5005];
bool cant[5005];
set<int> poss[5005];
void solve(int N) {
/*
int value = query(1, N);
for(int i = 1; i <= N; i++) {
answer(i, i);
}
*/
int low = 1,high = N;
// prefix
while(low != high){
int mid = (low+high)/2;
if(query(1,mid) == N-1){
high = mid;
}else low = mid+1;
}
int five = high;
low = 1, high = N;
while(low != high){
int mid = (low+high+1)/2;
if(query(mid,N) == N-1){
low = mid;
}else high = mid-1;
}
int one = low;
vector<int> A(N+1,0);
A[one] = 1;
A[five] = N;
cant[1] = 1;
cant[N] = 1;
poss[one].insert(1);
poss[five].insert(N);
int cnt = N-2;
for(int i=one-1;i>=1;i--){
int q = query(i,i+1);
for(auto x:poss[i+1]){
int nx = x+q;
if(nx > 1 && nx < N && !cant[nx]){
poss[i].insert(nx);
}
nx = x-q;
if(nx > 1 && nx < N && !cant[nx]){
poss[i].insert(nx);
}
}
if(poss[i].size() == 1){
cnt--;
A[i] = *(poss[i].begin());
cant[A[i]] = 1;
}
}
for(int i=one+1;i<five-1;i++){
int q = query(i-1,i);
for(auto x:poss[i-1]){
int nx = x+q;
if(nx > 1 && nx < N && !cant[nx]){
poss[i].insert(nx);
}
nx = x-q;
if(nx > 1 && nx < N && !cant[nx]){
poss[i].insert(nx);
}
}
if(poss[i].size() == 1){
cnt--;
A[i] = *(poss[i].begin());
cant[A[i]] = 1;
}
}
if(five-1 > one){
int q = query(five-1,five);
A[five-1]= N-q;
cant[A[five-1]] = 1;
poss[five-1].insert(A[five-1]);
cnt--;
}
for(int i=five+1;i<=N;i++){
int q = query(i-1,i);
for(auto x:poss[i-1]){
int nx = x+q;
if(nx > 1 && nx < N && !cant[nx]){
poss[i].insert(nx);
}
nx = x-q;
if(nx > 1 && nx < N && !cant[nx]){
poss[i].insert(nx);
}
}
if(poss[i].size() == 1){
cnt--;
A[i] = *(poss[i].begin());
cant[A[i]] = 1;
}
}
/*
while(cnt){
for(int i=1;i<=N;i++){
vector<int> er;
for(auto x:poss[i]){
if(cant[x])er.push_back(x);
}
for(auto x:er)poss[i].erase(x);
if(poss[i].size() == 1){
cnt--;
A[i] = *(poss[i].begin());
cant[A[i]] = 1;
}
}
}
*/
for(int i = 1; i <= N; i++) {
cerr<<i<<": ";
for(auto x:poss[i]){
cerr<<x<<" ";
}
cerr<<'\n';
}
for(int i = 1; i <= N; i++) {
answer(i, A[i]);
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |