QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#780163 | #1813. Joy with Permutations | andrewgopher | TL | 0ms | 0kb | C++14 | 3.8kb | 2024-11-25 02:59:37 | 2024-11-25 02:59:38 |
answer
#include "bits/stdc++.h"
using namespace std;
//#define fast ios_base::sync_with_stdio(0) , cin.tie(0) , cout.tie(0)
#define int long long
int med(int i,int j,int k){
cout << "? " << i << " " << j << " " << k << endl;
int ans;cin>>ans;
return ans;
}
bool lt(int i,int j){
cout << "? " << i << " " << j << endl;
int ans;cin>>ans;
return ans==i;
}
void solve() {
int n;
cin >> n;
//initialize
set<pair<int,int>> cur;
{
int qa = med(1,2,3);
int qb = med(1,2,4);
int qc = med(1,3,4);
int qd = med(2,3,4);
if (qa == qb){
if (qa < qc){
cur = {{qa,1},{qa,2},{qc,3},{qc,4}};
} else {
cur={{qc,3},{qc,4},{qa,1},{qa,2}};
}
} else if (qa == qc){
if (qa < qb){
cur={{qa,1},{qa,3},{qb,2},{qb,4}};
} else {
cur={{qb,2},{qb,4},{qa,1},{qa,3}};
}
} else if (qa==qd){
if (qa < qb){
cur={{qa,2},{qa,3},{qb,1},{qb,4}};
} else {
cur={{qb,1},{qb,4},{qa,2},{qa,3}};
}
}
}
for (int i = 5;i<=n;i++){
//query higher
auto curBack = *cur.rbegin();
auto curSecBackIt = cur.rbegin();
curSecBackIt--;
auto curSecBack = *curSecBackIt;
auto curFront = *cur.begin();
auto curSecFrontIt = cur.begin();
curSecFrontIt++;
auto curSecFront = *curSecFrontIt;
int secMin = curFront.first;
int secMax = curBack.first;
int ql = med(curFront.second, curSecBack.second,i);
int qh = med(curSecFront.second, curBack.second,i);
if (ql < secMin){
//update curFront to have value ql, insert i with value ql
cur.erase(curFront);
cur.insert({ql,curFront.second});
cur.insert({ql,i});
} else if (ql == secMin) {
//update curSecFront to have value qh, insert i with value qh
cur.erase(curSecFront);
cur.insert({qh,curSecFront.second});
cur.insert({qh,i});
} else if (ql > secMin && ql < secMax) {
//insert i with value ql
cur.insert({ql,i});
} else if (ql == secMax) {
//update curBack to have value qh, insert i with value qh
cur.erase(curBack);
cur.insert({qh,curBack.second});
cur.insert({qh,i});
} else if (ql>secMax) {
//update curSecBack to have value ql, insert i with value ql
cur.erase(curSecBack);
cur.insert({ql,curSecBack.second});
cur.insert({ql,i});
} else {
assert("oops wtf");
}
}
{
auto it = cur.begin();
int frontInd = it->second;
it++;
int secFrontInd = it->second;
if (lt(frontInd,secFrontInd)){
cur.erase(cur.begin());
cur.insert({1,frontInd});
} else {
cur.erase(it);
cur.insert({1,secFrontInd});
}
}
{
auto it2 =cur.rbegin();
int backInd = it2->second;
it2--;
int secBackInd = it2->second;
if (lt(backInd,secBackInd)){
cur.erase({it2->first,secBackInd});
cur.insert({n,secBackInd});
} else {
cur.erase({cur.rbegin()->first,backInd});
cur.insert({n,backInd});
}
}
vector<int> ans(n);
for (auto p : cur){
ans[p.second-1]=p.first;
}
cout << "! ";
for (int i =0;i<n;i++){
cout << ans[i] << " ";
}
cout << endl;
}
signed main() {
int t=1;
while (t--) solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Time Limit Exceeded
input:
5
output:
? 1 2 3