QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#297511 | #6303. Inversion | tangled | WA | 0ms | 3504kb | C++20 | 1.6kb | 2024-01-04 17:19:02 | 2024-01-04 17:19:02 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve()
{
int n;
cin >> n;
vector<int> a(n + 1), d(n + 1);
vector<vector<int>> dis(n + 1, vector<int>(n + 1));
for (int i = 0; i < n; i++)
d[i] = i;
auto ask = [&](int l, int r)
{
if (l >= r)
return 0;
cout << "? " << l << " " << r << endl;
int x;
cin >> x;
return x;
};
auto get = [&](int l, int r)
{
if (l >= r)
return 0;
return dis[l][r];
};
auto check = [&](int l, int r)
{
int cnt = 0;
cnt += ask(l, r);
cnt -= ask(l + 1, r);
cnt -= get(l, r - 1);
cnt += get(l + 1, r - 1);
return cnt;
};
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < i; j++)
a[d[j]] = j;
int l = 0, r = i;
while (l < r)
{
int mid = l + r >> 1;
if (check(a[mid], i))
r = mid;
else
l = mid + 1;
}
d[i] = l;
for (int j = 1; j < i; j++)
if (d[j] >= l)
d[j]++;
int cnt = 0;
for (int j = i - 1; j >= 0; j--)
{
if (d[j] > d[i])
cnt++;
dis[j][i] = (dis[j][i - 1] + cnt) % 2;
}
}
cout << "! ";
for (int i = 1; i <= n; i++)
cout << a[i] + 1 << " ";
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int tc = 1;
// cin >> tc;
while (tc--)
solve();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3504kb
input:
3
output:
? 0 1
result:
wrong output format Unexpected end of file - int32 expected