이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "xylophone.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template <class F, class _S>
bool chmin(F &u, const _S &v){
bool flag = false;
if ( u > v ){
u = v; flag |= true;
}
return flag;
}
template <class F, class _S>
bool chmax(F &u, const _S &v){
bool flag = false;
if ( u < v ){
u = v; flag |= true;
}
return flag;
}
//static int A[5000];
void solve(int n) {
int id = 1;
for(int i = 12; i >= 0; i--){
int to = min(n, id+(1<<i));
if(query(1, to) == n-1)continue;
id = to;
}
id++;
vector<int> df(n+1), us(n+1, 0);
us[1] = 1;
df[id] = 1;
if(id < n)df[id+1] = 1 + query(id, id+1),us[df[id+1]] = 1;
if(id > 1)df[id-1] = 1 + query(id-1, id),us[df[id-1]] = 1;
auto r = [&]() -> void{
for(int i = id+2; i <= n; i++){
int dif1 = query(i-1, i);
if(df[i-1]+dif1 > n)df[i] = df[i-1] - dif1;
else if(df[i-1]-dif1 < 1)df[i] = df[i-1] + dif1;
else if(us[df[i-1] - dif1])df[i] = df[i-1] + dif1;
else if(us[df[i-1] + dif1])df[i] = df[i-1] - dif1;
else if(df[i-2] > df[i-1]){
int dif2 = query(i-2, i);
if(dif2 == df[i-2] - df[i-1] + dif1)df[i] = df[i-1]-dif1;
else df[i] = df[i-1]+dif1;
}else{
int dif2 = query(i-2, i);
if(dif2 == df[i-1] - df[i-2] + dif1)df[i] = df[i-1]+dif1;
else df[i] = df[i-1]-dif1;
}
us[df[i]] = 1;
}
};r();
auto l = [&]() -> void{
for(int i = id-2; i > 0; i--){
int dif1 = query(i, i+1);
if(df[i+1]+dif1 > n)df[i] = df[i+1] - dif1;
else if(df[i+1]-dif1 < 1)df[i] = df[i+1] + dif1;
else if(us[df[i+1] - dif1])df[i] = df[i+1] + dif1;
else if(us[df[i+1] + dif1])df[i] = df[i+1] - dif1;
else if(df[i+2] > df[i+1]){
int dif2 = query(i, i+2);
if(dif2 == df[i+2] - df[i+1] + dif1)df[i] = df[i+1]-dif1;
else df[i] = df[i+1]+dif1;
}else{
int dif2 = query(i, i+2);
if(dif2 == df[i+1] - df[i+2] + dif1)df[i] = df[i+1]+dif1;
else df[i] = df[i+1]-dif1;
}
us[df[i]] = 1;
}
};l();
//for(int i = 1; i <= n; i++)cout << df[i] << ' ';
//cout << '\n';
for(int i = 1; i <= n; i++)
df[i] = n - df[i] + 1;
//cout << ch << '\n';
for(int i = 1; i <= n; i++){
answer(i, df[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... |