QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#795168#9818. Hash CollisionDarwinA66WA 2ms4032kbC++201.1kb2024-11-30 18:14:232024-11-30 18:14:23

Judging History

This is the latest submission verdict.

  • [2024-11-30 18:14:23]
  • Judged
  • Verdict: WA
  • Time: 2ms
  • Memory: 4032kb
  • [2024-11-30 18:14:23]
  • Submitted

answer

#include<bits/stdc++.h>
using namespace std;
int ask(int a,int b)
{
    printf("? %d %d\n",a,b);
    fflush(stdout);
    int res;
    scanf("%d",&res);
    return res;
}
void guess(int a,int b)
{
    printf("! %d %d\n",a,b);
    fflush(stdout);
}
int R(int n)
{
    srand(time(0));
    return rand()%n+1;
}
int base[2024];
int gs[2024];
map<int,int>fun;
int main()
{
    int n,s;
    int size;
    scanf("%d",&n);
    int bar=(int)(sqrt(n));
    s=ask(n,1);
    base[0]=s;
    fun[s]=1;
    for(int i=1;i<=bar;i++)
    {
        int x=ask(i,s);
        if(x==s)
        {
            size=i;
            int y=(size+(-s)%size)%size;
            guess(s,base[y]);
            return 0;
        }
        base[i]=x;
        fun[x]=i+1;
    }
    for(int i=2;i<=bar+1&&((i-1)*bar<=n);i++)
    {
        int x=ask((i-1)*bar,base[bar]);
        if(fun[x]!=0)
        {
            int bia=fun[x]-1;
            size=i*bar-bia;
            int y=(size+(-s)%size)%size;
            int t=ask(y,s);
            guess(s,t);
            return 0;
        }
    }
    return 0;
}

詳細信息

Test #1:

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

input:

6
2
3
5
2
5

output:

? 6 1
? 1 2
? 2 2
? 2 5
? 2 2
! 2 5

result:

ok 

Test #2:

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

input:

4
4
2
4

output:

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

result:

ok 

Test #3:

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

input:

1
1
1

output:

? 1 1
? 1 1
! 1 1

result:

ok 

Test #4:

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

input:

2
1
1

output:

? 2 1
? 1 1
! 1 1

result:

ok 

Test #5:

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

input:

2
1
1

output:

? 2 1
? 1 1
! 1 1

result:

ok 

Test #6:

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

input:

2
1
2
1
2

output:

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

result:

ok 

Test #7:

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

input:

2
2
2

output:

? 2 1
? 1 2
! 2 2

result:

ok 

Test #8:

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

input:

100000
1
1

output:

? 100000 1
? 1 1
! 1 1

result:

ok 

Test #9:

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

input:

100000
42
42

output:

? 100000 1
? 1 42
! 42 42

result:

ok 

Test #10:

score: 0
Accepted
time: 2ms
memory: 3860kb

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:

ok 

Test #11:

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

input:

100000
100000
100000

output:

? 100000 1
? 1 100000
! 100000 100000

result:

ok 

Test #12:

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

input:

3
1
1

output:

? 3 1
? 1 1
! 1 1

result:

ok 

Test #13:

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

input:

4
1
4
1

output:

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

result:

ok 

Test #14:

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

input:

5
3
4
3

output:

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

result:

ok 

Test #15:

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

input:

6
6
2
6

output:

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

result:

ok 

Test #16:

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

input:

7
3
3

output:

? 7 1
? 1 3
! 3 3

result:

ok 

Test #17:

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

input:

8
2
4
1
6
4
8

output:

? 8 1
? 1 2
? 2 2
? 2 1
? 4 1
? 3 2
! 2 8

result:

ok 

Test #18:

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

input:

9
8
8

output:

? 9 1
? 1 8
! 8 8

result:

ok 

Test #19:

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

input:

10
6
9
1
3
1
1

output:

? 10 1
? 1 6
? 2 6
? 3 6
? 3 3
? 2 6
! 6 1

result:

ok 

Test #20:

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

input:

11
9
9

output:

? 11 1
? 1 9
! 9 9

result:

ok 

Test #21:

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

input:

12
10
2
10

output:

? 12 1
? 1 10
? 2 10
! 10 10

result:

ok 

Test #22:

score: -100
Wrong Answer
time: 0ms
memory: 3880kb

input:

13
5
9
4
10
9

output:

? 13 1
? 1 5
? 2 5
? 3 5
? 3 10
? 0 5

result:

wrong answer Integer parameter [name=c] equals to 0, violates the range [1, 13]