QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#795077 | #9818. Hash Collision | Evan | TL | 0ms | 0kb | C++23 | 1.1kb | 2024-11-30 17:48:18 | 2024-11-30 17:48:19 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
int ask(int b,int a)
{
printf("? %d %d\n",a,b);
int res;
scanf("%d",&res);
fflush(stdout);
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: 0
Time Limit Exceeded
input:
6