QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#600686 | #6303. Inversion | ucup-team3691# | RE | 1ms | 3612kb | C++14 | 1.9kb | 2024-09-29 18:22:31 | 2024-09-29 18:22:31 |
Judging History
answer
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <cassert>
#include <algorithm>
#include <cmath>
#include <random>
#include <ctime>
#include <cstdlib>
#include <chrono>
using namespace std;
map<pair<int, int>, int> f;
int query(int l, int r) {
if (f.count({l, r})) {
return f[{l, r}];
}
if (l == r) {
return 0;
}
cout << "? " << l << " " << r << endl;
cin >> f[{l, r}];
return f[{l, r}];
}
int comp(int l, int r) {
if (r - l == 1) {
return query(l, r);
}
int st = query(l, r - 1);
int dr = query(l + 1, r);
int all = query(l, r);
int mid = query(l + 1, r - 1);
return st ^ dr ^ all ^ mid;
}
vector<int> divide(int l, int r) {
if (l == r) {
return {1};
}
if (l == r - 1) {
if (comp(l, r) == 0) {
return {1, 2};
} else {
return {2, 1};
}
}
int m = (l + r) / 2;
auto st = divide(l, m);
auto dr = divide(m + 1, r);
map<int, int> fs, fd;
for (int i = 0; i < st.size(); ++i) {
fs[st[i]] = i + l;
}
for (int i = 0; i < dr.size(); ++i) {
fd[dr[i]] = i + m + 1;
}
vector<int> v(r - l + 1);
int i = 1, j = 1, k = 1;
while (i <= st.size() && j <= dr.size()) {
if (comp(fs[i], fd[j]) == 0) {
v[fs[i++] - 1] = k++;
} else {
v[fd[j++] - 1] = k++;
}
}
while (i <= st.size()) {
v[fs[i++] - 1] = k++;
}
while (j <= dr.size()) {
v[fd[j++] - 1] = k++;
}
return v;
}
void solve() {
int n;
cin >> n;
auto v = divide(1, n);
cout << "! ";
for (auto it : v) {
cout << it << " ";
}
cout << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
//cin >> t;
while (t--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3612kb
input:
3 0 1 0
output:
? 1 2 ? 2 3 ? 1 3 ! 2 3 1
result:
ok OK, guesses=3
Test #2:
score: -100
Runtime Error
input:
1993 0 0 0 0 0 0 1 0 1 0
output:
? 1 2 ? 3 4 ? 2 3 ? 1 3 ? 5 6 ? 7 8 ? 6 7 ? 5 7 ? 6 8 ? 5 8 ? 1 -1