QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#741802#9734. Identify Chorducup-team902WA 10ms3796kbC++173.2kb2024-11-13 15:15:012024-11-13 15:15:01

Judging History

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

  • [2024-12-08 22:59:51]
  • hack成功，自动添加数据
  • (/hack/1274)
  • [2024-11-13 15:15:01]
  • 评测
  • 测评结果：WA
  • 用时：10ms
  • 内存：3796kb
查看
  • [2024-11-13 15:15:01]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
int n;
int query(int u, int v)
{
    u = (u % n + n) % n;
    v = (v % n + n) % n;
    printf("? %d %d\n", u + 1, v + 1);
    fflush(stdout);
    int d;
    scanf("%d", &d);
    return d;
}
void answer(int u, int v)
{
    u = (u % n + n) % n;
    v = (v % n + n) % n;
    printf("! %d %d\n", u + 1, v + 1);
    fflush(stdout);
    int t;
    scanf("%d", &t);
    // assert(t == 1);
}
void solve()
{
    scanf("%d", &n);
    if (n & 1)
    {
        int u = 0, v = n / 2, d;
        while (1)
        {
            d = query(u, v);
            if (d != n / 2)
                break;
            v++;
            swap(u, v);
        }
        if (d == 1)
        {
            answer(u, v);
            return;
        }
        if (query(u, v + 1) == d - 1)
        {
            int len = n / 2 - (d - 1) + 1;
            int l = len, r = n / 2;
            while (l <= r)
            {
                int mid = l + r >> 1;
                if (query(u, u - mid) == mid - len + 1)
                    r = mid - 1;
                else
                    l = mid + 1;
            }
            l = u - l;
            if (query(l + len, l) == 1)
                answer(l + len, l);
            else
                answer(2 * u - (l + len), l);
        }
        else
        {
            int len = n / 2 - d + 1;
            int l = len, r = n / 2;
            while (l <= r)
            {
                int mid = l + r >> 1;
                if (query(u, u + mid) == mid - len + 1)
                    r = mid - 1;
                else
                    l = mid + 1;
            }
            if (query(l - len, l) == 1)
                answer(l - len, l);
            else
                answer(2 * u - (l - len), l);
        }
    }
    else
    {
        int st = 0, d;
        while (1)
        {
            d = query(st, st + n / 2);
            if (d != n / 2)
                break;
            st++;
        }
        if (d == 1)
        {
            answer(st, st + n / 2);
            return;
        }
        int len = n / 2 - d + 1;
        if (query(st, st + n / 2 - 1) == d - 1)
        {
            int l = len, r = n / 2;
            while (l <= r)
            {
                int mid = l + r >> 1;
                if (query(st, st + mid) == mid - len + 1)
                    r = mid - 1;
                else
                    l = mid + 1;
            }
            l += st;
            if (query(l - len, l) == 1)
                answer(l - len, l);
            else
                answer(2 * st - (l - len), l);
        }
        else
        {
            int l = len, r = n / 2;
            while (l <= r)
            {
                int mid = l + r >> 1;
                if (query(st, st - mid) == mid - len + 1)
                    r = mid - 1;
                else
                    l = mid + 1;
            }
            l = st - l;
            if (query(l + len, l) == 1)
                answer(l + len, l);
            else
                answer(2 * st - (l + len), l);
        }
    }
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
        solve();
    return 0;
}
Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

2
6
2
2
2
2
2
1
4
1
1

output:

? 1 4
? 1 3
? 1 5
? 1 4
? 6 4
! 2 4
? 1 3
! 1 3

result:

ok ok (2 test cases)

Test #2:

score: -100
Wrong Answer
time: 10ms
memory: 3796kb

input:

1000
15
5
6
5
6
5
1
1
19
5
4
4
3
5
1
17
5
4
4
3
5
1
15
6
7
3
1
1
1
14
5
4
3
3
2
1
1
15
3
2
3
2
3
1
17
8
8
8
7
6
5
5
4
3
1
20
6
5
3
1
1
1
13
5
6
4
4
2
1
18
3
4
2
3
1
1
13
4
3
2
3
1
1
14
2
3
3
2
1
1
17
8
7
6
3
3
2
3
1
12
5
5
3
2
3
2
1
10
5
5
3
4
4
3
3
1
14
6
6
4
6
6
2
1
19
8
7
4
4
3
1
1
19
6
5
3
3
2
3...

output:

? 1 8
? 1 9
? 1 6
? 1 7
? 1 8
? 5 8
! 5 8
? 1 10
? 1 11
? 1 13
? 1 12
? 18 12
! 3 12
? 1 9
? 1 10
? 1 12
? 1 11
? 16 11
! 3 11
? 1 8
? 1 9
? 1 5
? 1 3
? 1 3
! 1 3
? 1 8
? 1 7
? 1 6
? 1 4
? 1 5
? 2 5
! 2 5
? 1 8
? 1 9
? 1 10
? 1 9
? 15 9
! 2 9
? 1 9
? 10 1
? 2 10
? 11 2
? 11 3
? 11 6
? 11 4
? 11 5
? ...

result:

wrong answer Wrong answer n=15, actual=11-13, guessed=15-5 (test case 43)
English 繁體中文 简体中文

Server Time: 2025-02-01 19:44:26 | OpenSource Project