QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#780163#1813. Joy with PermutationsandrewgopherTL 0ms0kbC++143.8kb2024-11-25 02:59:372024-11-25 02:59:38

Judging History

你现在查看的是最新测评结果

  • [2024-11-25 02:59:38]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [2024-11-25 02:59:37]
  • 提交

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;
}

详细

Test #1:

score: 0
Time Limit Exceeded

input:

5

output:

? 1 2 3

result: