QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#333616#6303. InversionautomacRE 1ms3860kbC++202.4kb2024-02-20 10:15:212024-02-20 10:15:21

Judging History

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

  • [2024-02-20 10:15:21]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3860kb
  • [2024-02-20 10:15:21]
  • 提交

answer

#include <bits/stdc++.h>

#define forn(i, n) for(int i = 0; i < (int)n; ++i)
#define for1(i, n) for(int i = 1; i <= (int)n; ++i)
#define fore(i, l, r) for(int i = (int)l; i <= (int)r; ++i)
#define fored(i, l, r) for(int i = (int)r; i >= (int)l; --i)
#define all(x) x.begin(), x.end()
#define el '\n'
#define d(x) cerr << #x << ' ' << x << el

#define sz(a) (int) a.size()
#define pb push_back
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef array<int, 4> a4;
typedef pair<int,int> ii;
typedef tuple<ll,int,int> iii;
const int nax = 2e5;
// const int nax = 2e3;

const ll inf = 1e17;
// void show(vi &v){
//     for(int x : v)cout<<x<<" ";
//     cout<<el;
// }
int qs = 0;
map<ii, int> queries;
bool find(int i, int j){
    if(i==j)return 0;
    assert(i < j);
    if(queries.find({i,j}) != queries.end()){
        return queries[{i,j}];
    }
    ++qs;
    cout<<"? "<<i<<" "<<j<<el;
    cout.flush();
    bool parity;
    cin>>parity;
    queries[{i,j}] = parity;
    assert(qs <= 40000);
    return parity;
}

bool isGreater(int i, int j){
    if(abs(j-i) == 1) return find(i,j);
    assert(i < j);
    int allRange = find(i, j);
    int excL = find(i+1, j), excR = find(i, j-1);
    int excAll = find(i+1, j-1);
    if(((excL + excR - excAll + 2) % 2) != allRange) return 1;
    return 0;

}
void solve(){
    int n;
    cin>>n;
    if(n == 1){
        cout<<"! 1"<<endl;
        return;
    }
    vi v(n);
    iota(all(v), 1);
    if(isGreater(v[0],v[1])) swap(v[0], v[1]);

    fore(i,2,n-1){
        int lo = -1, hi = i;
        while(lo + 1 < hi){
            int mid = lo + (hi-lo)/2;
            if(isGreater(v[mid], v[i])){
                hi = mid;
            }else lo = mid;
        }
        // d(hi);
        // show(v);
        fored(j, hi, i-1){
            swap(v[j], v[j+1]);
        }
        // show(v);
    }

    vi ans(n);
    forn(i,n){
        ans[v[i]-1] = i+1;
    }
    cout<<"! ";
    forn(i,n){
        cout<<ans[i];
        if(i!=n-1) cout<<" ";
    }
    cout<<el;
    cout.flush();
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tt = 1;
    // cin>>tt;
    while(tt--){
        solve();
    }
}

/**
 * aprendizaje: 
 * Fijar 2 elementos y pensar como ordenarlos. Pensar en reducir la cantidad de consultas
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3860kb

input:

3
0
0
1

output:

? 1 2
? 1 3
? 2 3
! 2 3 1

result:

ok OK, guesses=3

Test #2:

score: -100
Runtime Error

input:

1993
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
1
0
1
0
0
0
1
0
1
1
1
1
1
1
1
0
1
1
1
1
1
0
0
1
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
0
0
1
0
0
1
1
0
0
1
1
0
0
1
1
1
1
0
1
1
0
0
0
1
0
1
1
1
0
1
0
0
1
0
0
0
0
1
0
1
0
0
1
0
1
0
0
1
1
0
1
1
1
0
1
0
0
0
1
1
0
1
1
1
1
1
1
0
0
0
1
0
0
0
0
1
0
1
1
0
1
1
0
0
0
0
1
0
0
1...

output:

? 1 2
? 1 3
? 2 3
? 2 4
? 3 4
? 2 5
? 3 5
? 1 5
? 1 4
? 2 6
? 3 6
? 5 6
? 1 6
? 1 7
? 2 7
? 5 7
? 6 7
? 1 8
? 2 8
? 3 8
? 4 8
? 3 7
? 4 7
? 1 9
? 2 9
? 8 9
? 3 9
? 9 10
? 5 10
? 6 10
? 5 9
? 6 9
? 7 10
? 8 10
? 7 9
? 1 11
? 2 11
? 1 10
? 2 10
? 8 11
? 9 11
? 10 11
? 11 12
? 8 12
? 9 12
? 10 12
? 2 1...

result: