이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "permutation.h"
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for (int i=(a);i>=(b);--i)
using ll=long long;
using ii=pair<int,int>;
void solve(int N) {
vector<int> V(N);
iota(ALL(V),1);
int mid;
vector<ii> lh, rh;
{
int q1 = query(V);
swap(V[0],V[1]);
int q2 = query(V);
swap(V[0],V[1]);
swap(V[1],V[2]);
int q3 = query(V);
swap(V[0],V[1]);
int q4 = query(V);
swap(V[0],V[1]);
swap(V[1],V[2]);
swap(V[0],V[2]);
swap(V[0],V[1]);
int q5 = query(V);
swap(V[0],V[1]);
int q6 = query(V);
swap(V[0],V[2]);
if (q1-q2 > 0) {
if (q3-q4 > 0) {
mid = 1;
lh = {ii(2,q1-q2)};
rh = {ii(3,q3-q4)};
} else {
mid = 3;
rh = {ii(1,q4-q3)};
lh = {ii(2,q4-q3+(q1-q2))};
}
} else {
if (q3-q4 > 0) {
mid = 2;
lh = {ii(1,q2-q1)};
rh = {ii(3,q2-q1+(q3-q4))};
} else {
if (q5-q6 > 0) {
mid = 2;
rh = {ii(3,q5-q6)};
lh = {ii(1,q2-q1)};
} else {
mid = 3;
lh = {ii(2,q6-q5)};
rh = {ii(1,q4-q3)};
}
}
}
}
//~ for (auto x : lh) { cout << x.first << ' ' << x.second << " :: "; } cout << endl;
//~ for (auto x : rh) { cout << x.first << ' ' << x.second << " :: "; } cout << endl;
if (N > 3) {
//~ TRACE(mid _ rh[0].first);
FOR(i,0,N-1) if (V[i] == mid) swap(V[0],V[i]);
FOR(i,0,N-1) if (V[i] == rh[0].first) swap(V[1],V[i]);
FOR(i,3,N-1){
swap(V[2],V[i]);
int q1 = query(V);
swap(V[0],V[1]);
int q2 = query(V);
swap(V[0],V[1]);
if (abs(q2-q1) < rh[0].second) {
//~ TRACE("R" _ (q2-q1+rh[0].second)/2);
rh.push_back(ii(i+1,(q2-q1+rh[0].second)/2));
} else {
if (q2-q1 < 0) {
swap(V[1],V[2]);
int q3 = query(V);
swap(V[0],V[1]);
int q4 = query(V);
swap(V[0],V[1]);
swap(V[1],V[2]);
//~ TRACE("L" _ q3-q4);
lh.push_back(ii(i+1,q3-q4));
} else {
swap(V[0],V[2]);
int q3 = query(V);
swap(V[0],V[1]);
int q4 = query(V);
swap(V[0],V[1]);
swap(V[0],V[2]);
//~ TRACE("R" _ q4-q3);
rh.push_back(ii(i+1,q4-q3+rh[0].second));
}
}
swap(V[2],V[i]);
}
}
sort(ALL(lh),[](ii a, ii b){ return a.second > b.second; });
sort(ALL(rh),[](ii a, ii b){ return a.second < b.second; });
vector<int> sorted;
for (auto x : lh) sorted.push_back(x.first);
sorted.push_back(mid);
for (auto x : rh) sorted.push_back(x.first);
vector<int> P(N);
FOR(i,0,N-1) P[sorted[i]-1] = i+1;
//~ for (auto x : sorted) { cout << x << ' '; } cout << endl;
//~ for (auto x : lh) { cout << x.first << ' ' << x.second << " :: "; } cout << endl;
//~ for (auto x : rh) { cout << x.first << ' ' << x.second << " :: "; } cout << endl;
//~ for (int x : P) { cout << x << ' '; } cout << endl;
answer(P);
}
컴파일 시 표준 에러 (stderr) 메시지
stub.cpp: In function 'int query(int*)':
stub.cpp:15:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf(stdin, "%d", &x);
~~~~~~^~~~~~~~~~~~~~~~~
stub.cpp: In function 'int main(int, char**)':
stub.cpp:48:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fscanf(stdin, "%d", &N);
~~~~~~^~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |