QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#805116#9818. Hash Collisionucup-team3723#TL 1ms3836kbC++141.2kb2024-12-08 13:30:052024-12-08 13:30:06

Judging History

This is the latest submission verdict.

  • [2024-12-08 13:30:06]
  • Judged
  • Verdict: TL
  • Time: 1ms
  • Memory: 3836kb
  • [2024-12-08 13:30:05]
  • Submitted

answer

#include <bits/stdc++.h>
#define dbg(x) cerr << #x << ':'<< (x) << endl;
#define ALL(x) x.begin(),x.end()
using namespace std;
using ll = long long;
using ld = long double;

int main() {
    const int block = 450;
    int n;
    cin >> n;
    map<int, int> mp;
    int base;
    cout << "? " << n << " " << 1 << endl;
    cin >> base;
    mp[base] = 0;
    int t = 0;
    for (int i = 1; i < block; ++i)
    {
        cout << "? " << i << ' ' << base << endl;
        int id;
        cin >> id;
        if (id == base)
        {
            t = i;
            break;
        }
        mp[id] = i;
    }
    if (t == 0)
    {
        for (int i = 1; i * block <= n; ++i)
        {
            int tmp = i * block;
            cout << "? " << tmp << ' ' << base << endl;
            int id;
            cin >> id;
            if (mp.find(id) != mp.end())
            {
                t = tmp - mp[id];
                break;
            }
        }
    }
    
    int tmp = -base;
    while (tmp <= 0) tmp += t;
    cout << "? " << tmp << ' ' << base << endl;
    int ans_r;
    cin >> ans_r;
    // cout << "? " << base << ' ' << ans_r << endl;
    cout << "! " << base << ' ' << ans_r << endl;
    
}

详细

Test #1:

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

input:

6
2
3
5
4
2
5

output:

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

result:

ok 

Test #2:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

4
4
2
4
4

output:

? 4 1
? 1 4
? 2 4
? 2 4
! 4 4

result:

ok 

Test #3:

score: 0
Accepted
time: 1ms
memory: 3588kb

input:

1
1
1
1

output:

? 1 1
? 1 1
? 1 1
! 1 1

result:

ok 

Test #4:

score: 0
Accepted
time: 1ms
memory: 3588kb

input:

2
1
1
1

output:

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

result:

ok 

Test #5:

score: 0
Accepted
time: 0ms
memory: 3648kb

input:

2
1
1
1

output:

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

result:

ok 

Test #6:

score: 0
Accepted
time: 1ms
memory: 3616kb

input:

2
1
2
1
2

output:

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

result:

ok 

Test #7:

score: 0
Accepted
time: 1ms
memory: 3820kb

input:

2
2
2
2

output:

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

result:

ok 

Test #8:

score: 0
Accepted
time: 1ms
memory: 3548kb

input:

100000
1
1
1

output:

? 100000 1
? 1 1
? 1 1
! 1 1

result:

ok 

Test #9:

score: 0
Accepted
time: 1ms
memory: 3836kb

input:

100000
42
42
42

output:

? 100000 1
? 1 42
? 1 42
! 42 42

result:

ok 

Test #10:

score: -100
Time Limit Exceeded

input:

100000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
1...

output:

? 100000 1
? 1 1
? 2 1
? 3 1
? 4 1
? 5 1
? 6 1
? 7 1
? 8 1
? 9 1
? 10 1
? 11 1
? 12 1
? 13 1
? 14 1
? 15 1
? 16 1
? 17 1
? 18 1
? 19 1
? 20 1
? 21 1
? 22 1
? 23 1
? 24 1
? 25 1
? 26 1
? 27 1
? 28 1
? 29 1
? 30 1
? 31 1
? 32 1
? 33 1
? 34 1
? 35 1
? 36 1
? 37 1
? 38 1
? 39 1
? 40 1
? 41 1
? 42 1
? 43...

result: