이 제출은 이전 버전의 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 mx = 0, id = 1;
for(int i = 2; i <= n; i++){
if(chmax(mx, query(1, i)))id = i;
}
vector<int> df(n+1), us(n+1, 0);
int last = 0;
us[1] = id;
df[id] = 1;
for(int i = id+1; i <= n; i++){
int dif = query(i-1, i), cur = 0;
if(df[i-1]+dif > n)cur = df[i-1] - dif;
else if(df[i-1]-dif < 1)cur = df[i-1] + dif;
else if(us[df[i-1] - dif])cur = df[i+1] + dif;
else if(us[df[i-1] + dif])cur = df[i-1] - dif;
else{
int dif1 = query(id, i);
if(chmax(last, dif1))cur = dif1 + 1;
else cur = df[i-1] - dif;
}
us[cur] = i;
df[i] = cur;
chmax(last, df[i] - 1);
}
last = 0;
for(int i = id-1; i > 0; i--){
int dif = query(i, i+1), cur = 0;
if(df[i+1]+dif > n)cur = df[i+1] - dif;
else if(df[i+1]-dif < 1)cur = df[i+1] + dif;
else if(us[df[i+1] - dif])cur = df[i+1] + dif;
else if(us[df[i+1] + dif])cur = df[i-1] - dif;
else{
int dif1 = query(i, id);
if(chmax(last, dif1))cur = dif1 + 1;
else cur = df[i+1] - dif;
}
us[cur] = i;
df[i] = cur;
chmax(last, df[i] - 1);
}
//for(int i = 1; i <= n; i++)cout << df[i] << ' ';
//cout << '\n';
bool ch = 0;
for(int i = 1; i <= id; i++)if(df[i] == n)ch = 1;
if(ch)
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... |