QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#332834 | #6303. Inversion | Scano | WA | 76ms | 19268kb | C++20 | 1.8kb | 2024-02-19 16:10:20 | 2024-02-19 16:10:20 |
Judging History
answer
#include <bits/stdc++.h>
#define sz(v) v.size()
#define forn(i,n) for(int i = 0; i < n; ++i)
#define fi first
#define se second
#define el endl
#define all(v) v.begin(),v.end()
#define pb push_back
#define d(x) cout << #x << " : " << x << el
using namespace std;
typedef pair<int,int> ii;
typedef long long ll;
typedef tuple<ll,int,int> iii;
int dr[] = {1,0,-1,0};
int dc[] = {0,1,0,-1};
const int nax = 2000;
int mp[nax][nax];
vector<int> arr;
int preguntas = 0;
int get(int l, int r){
if(l == r) return 0;
if(mp[l][r]!=-1) return mp[l][r];
++preguntas;
cout << "? " << l + 1 << " " << r + 1 << el;
int x;
cin >> x;
return mp[l][r] = x;
}
int ask(int l, int r){
if(l+1==r){
return get(l, r);
}
int vlr = get(l, r);
int vl_r = get(l+1,r);
int vlr_ = get(l, r-1);
int vl_r_ = get(l+1, r-1);
return ((vlr - vl_r - vlr_ + vl_r_)%2 + 2)%2;
}
void solve(vector<int> &pos, int start = 0){
int r = rand()%sz(pos);
vector<int> ls, rs;
int cnt = 0;
forn(i,sz(pos)){
if(i == r) continue;
int val = 0;
if(i < r){
val = ask(pos[i], pos[r]);
if(val == 0){
++cnt;
ls.pb(pos[i]);
}else{
rs.pb(pos[i]);
}
}else{
val = ask(pos[r], pos[i]);
if(val == 1){
ls.pb(pos[i]);
++cnt;
}else{
rs.pb(pos[i]);
}
}
}
arr[pos[r]] = start + 1 + cnt;
if(sz(ls)) solve(ls, start);
if(sz(rs)) solve(rs, arr[pos[r]]);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cout << setprecision(20)<< fixed;
memset(mp, -1, sizeof mp);
int n;
cin >> n;
arr.resize(n);
vector<int> pos;
forn(i,n){
pos.pb(i);
}
solve(pos);
cout << "! ";
forn(i,n){
cout << arr[i] << " ";
}
cout << el;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 19212kb
input:
3 0 1 0
output:
? 1 2 ? 2 3 ? 1 3 ! 2 3 1
result:
ok OK, guesses=3
Test #2:
score: -100
Wrong Answer
time: 76ms
memory: 19268kb
input:
1993 0 1 1 1 0 1 1 1 0 1 1 0 1 1 1 1 0 1 0 0 0 0 1 0 1 1 0 1 1 0 1 1 1 0 1 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 1 1 0 0 1 1 0 1 0 0 0 0 0 1 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 0 1 1 1 0 0 0 1 0 0 1 1 1 1 1 1 0 0 0 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1 1 0 1 0 1 1 1 1 0 0 0 0 1 1 1 0 1 1 1...
output:
? 1 575 ? 2 575 ? 1 574 ? 2 574 ? 3 575 ? 3 574 ? 4 575 ? 4 574 ? 5 575 ? 5 574 ? 6 575 ? 6 574 ? 7 575 ? 7 574 ? 8 575 ? 8 574 ? 9 575 ? 9 574 ? 10 575 ? 10 574 ? 11 575 ? 11 574 ? 12 575 ? 12 574 ? 13 575 ? 13 574 ? 14 575 ? 14 574 ? 15 575 ? 15 574 ? 16 575 ? 16 574 ? 17 575 ? 17 574 ? 18 575 ? 1...
result:
wrong output format Unexpected end of file - int32 expected