QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#297506 | #6303. Inversion | tangled | WA | 0ms | 3600kb | C++20 | 1.7kb | 2024-01-04 17:08:34 | 2024-01-04 17:08:34 |
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 = 1; i <= n; i++)
{
a[i] = 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 = 2; i <= n; i++)
{
int l = 1, r = i - 1;
while (l < r)
{
int mid = l + r >> 1;
if (check(a[mid], i))
r = mid;
else
l = mid + 1;
}
for (int j = i; j > l; j--)
{
a[j] = a[j - 1];
d[a[j - 1]]++;
}
a[l] = i;
d[i] = l;
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] << " ";
}
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: 3600kb
input:
3 1
output:
? 2 3 ! 3 2 1
result:
wrong answer Wa.