QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#301878#6303. InversionwyWA 313ms19240kbC++141.9kb2024-01-10 13:45:272024-01-10 13:45:28

Judging History

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

  • [2024-01-10 13:45:28]
  • 评测
  • 测评结果:WA
  • 用时:313ms
  • 内存:19240kb
  • [2024-01-10 13:45:27]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

const int N = 2010;

int n, m;
int a[N], ans[N];
int f[N][N];
int cnt = 1;
int tr[N];

int lowbit(int x) { return x & -x; }

int query(int k)
{
    int res = 0;
    for (; k; k -= lowbit(k))
        res += tr[k];
    return res;
}

void add(int k)
{
    for (; k < N; k += lowbit(k))
        tr[k]++;
}

int get(int l, int r)
{
    if (~f[l][r])
        return f[l][r];
    cout << "? " << l << ' ' << r << '\n';
    cout.flush();
    cin >> f[l][r];

    cnt++;
    assert(cnt < 40000);

    return f[l][r];
}

int calc(int l, int r)
{
    if (~f[l][r])
        return f[l][r];

    memset(tr, 0, sizeof tr);
    int res = 0;
    for (int i = l; i <= r; i++)
    {
        add(ans[i]);
        res += query(n) - query(ans[i]);
    }

    return f[l][r] = res % 2;
}

bool check(int l, int r)
{
    return get(l, r) - get(l + 1, r) - calc(l, r - 1) + calc(l + 1, r - 1);
}

void solve()
{
    cin >> n;
    if (n == 1)
    {
        cout << "! 1" << '\n';
        cout.flush();
        return;
    }

    memset(f, -1, sizeof f);
    for (int i = 1; i <= n; i++)
        f[i][i] = 0;

    a[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        int l = 0, r = i;
        while (l + 1 != r)
        {
            int mid = l + r >> 1;
            if (check(a[mid], i)) // a[mid] > i
                r = mid;
            else
                l = mid;
        }

        for (int j = i - 1; j > l; j--)
            a[j + 1] = a[j];
        a[l + 1] = i;

        for (int j = 1; j <= i; j++)
            ans[a[j]] = j;
    }

    for (int i = 1; i <= n; i++)
        ans[a[i]] = i;

    cout << "!";
    for (int i = 1; i <= n; i++)
        cout << ' ' << ans[i];
    cout.flush();
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    solve();

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 19240kb

input:

3
0
0
1

output:

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

result:

ok OK, guesses=3

Test #2:

score: -100
Wrong Answer
time: 313ms
memory: 19192kb

input:

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

output:

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

result:

wrong answer Wa.