QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#795082#9818. Hash CollisionEvanWA 1ms4040kbC++231.1kb2024-11-30 17:49:352024-11-30 17:49:36

Judging History

This is the latest submission verdict.

  • [2024-11-30 17:49:36]
  • Judged
  • Verdict: WA
  • Time: 1ms
  • Memory: 4040kb
  • [2024-11-30 17:49:35]
  • Submitted

answer

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

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

6
2
3
5
4
5
5

output:

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

result:

ok 

Test #2:

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

input:

4
4
2
4

output:

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

result:

ok 

Test #3:

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

input:

1
1
1

output:

? 1 1
? 1 1
! 1 1

result:

ok 

Test #4:

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

input:

2
1
1

output:

? 2 1
? 1 1
! 1 1

result:

ok 

Test #5:

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

input:

2
1
1

output:

? 2 1
? 1 1
! 1 1

result:

ok 

Test #6:

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

input:

2
1
2
1

output:

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

result:

ok 

Test #7:

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

input:

2
2
2

output:

? 2 1
? 1 2
! 2 2

result:

ok 

Test #8:

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

input:

100000
1
1

output:

? 100000 1
? 1 1
! 1 1

result:

ok 

Test #9:

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

input:

100000
42
42

output:

? 100000 1
? 1 42
! 42 42

result:

ok 

Test #10:

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

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:

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