QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#678196#6303. InversionTggdb#WA 93ms7488kbC++201.8kb2024-10-26 14:16:252024-10-26 14:16:26

Judging History

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

  • [2024-10-26 14:16:26]
  • 评测
  • 测评结果:WA
  • 用时:93ms
  • 内存:7488kb
  • [2024-10-26 14:16:25]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
using namespace std;
map<pair<int, int>, int>mp;
int ques(int l, int r)
{
    int s1;
    if (mp[{l, r}] != 0)
    {
        return mp[{l, r}] - 1;
    }
    else
    {
        cout << "? " << l << " " << r << endl;
        int op;
        cin >> op;
        mp[{l,r}] = op + 1;
        return op;
    }
}
bool check(int sub,int now)
{
    int s1;
    if (sub + 1 == now)
    {
        s1 = ques(sub, now);
    }
    else
    {
        s1 = ques(sub, now) ^ ques(sub + 1, now) ^ ques(sub, now - 1) ^ ques(sub + 1, now - 1);
    }
    if (s1 == 1)
    {
        return 0;
    }
    else
    {
        return 1;
    }
}
int anwall[100000];
void solve()
{
    int n;
    cin >> n;
    vector<int>ve;
    ve.push_back(1);
    for (int i = 2; i <= n; i++)
    {
        int l = 0;
        int r = ve.size();
        int fl1 = 0, fl2 = 0;
        int anw;
        while (l < r)
        {
            int sub = (l + r) >> 1;
            if (check(ve[sub],i))
            {
                l = sub+1;
                fl1 = 1;
                anw = sub;
            }
            else
            {
                r = sub;
                fl2 = 1;
            }
        }
        if (fl1 == 0)
        {
            ve.insert(ve.begin(), i);
        }
        else if (fl2 == 0)
        {
            ve.push_back(i);
        }
        else
        {
            ve.insert(ve.begin() + anw + 1, i);
        }
    }
    for (int i = 1; i <= n; i++)
    {
        anwall[ve[i - 1]] = i;
    }
    cout << "! ";
    for (int i = 1; i <= n; i++)
    {
        cout << anwall[i] << " ";
    }
}
int main(void)
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    solve();
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3540kb

input:

3
0
1
0
0

output:

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

result:

ok OK, guesses=4

Test #2:

score: -100
Wrong Answer
time: 93ms
memory: 7488kb

input:

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

output:

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

result:

wrong output format Unexpected end of file - int32 expected