QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #183385 | #5375. Search | Lynkcat | 10 | 1141ms | 52692kb | C++20 | 3.6kb | 2023-09-19 14:31:28 | 2023-09-19 14:31:29 |
Judging History
answer
#include <bits/stdc++.h>
#include "search.h"
#define poly vector<int>
#define IOS ios::sync_with_stdio(false)
#define ll long long
#define mp make_pair
#define mt make_tuple
#define pa pair < int,int >
#define fi first
#define se second
#define inf 1e18
#define mod 998244353
#define sz(x) ((int)((x).size()))
// #define int ll
using namespace std;
namespace query
{
const int N=2005;
int f[N][N];
int n;
int bnd[N],pos[N];
int mx,my;
mt19937_64 rnd(time(0));
void geta(int k,int x,int y)
{
if (!x) return;
int l=pos[k]+1,r=bnd[k];
while (l<=r)
{
int mid=l+(r-l)/2;
mid=l;
if (ask1(mid,k,x,y)=="<")
{
pos[k]=mid;
l=mid+1;
} else r=mid-1;
}
}
void getb(int k,int x,int y)
{
int l=pos[k]+1,r=bnd[k];
while (l<=r)
{
int mid=l+(r-l)/2;
mid=r;
if (ask1(mid,k,x,y)=="<")
{
l=mid+1;
} else
{
bnd[k]=mid-1;
r=mid-1;
}
}
}
inline int calc(int x,int y)
{
return max((f[x][y]-1),(f[n][n]-f[x-1][n]-f[n][y-1]+f[x-1][y-1]-1));
}
int solve()
{
bool bl=1;
for (int i=1;i<=n;i++)
if (pos[i]==bnd[i]) bl&=1;
else bl=0;
int tot=0;
poly g;
for (int i=1;i<=n;i++)
{
tot+=bnd[i]-pos[i];
if (bnd[i]!=pos[i]) g.push_back(i);
}
if (bl) return 1;
int sm=tot;
int od=rnd()%sm;
sm=0;
int cx=0,cy=0;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
f[i][j]=0;
}
}
for (int j=1;j<=n;j++)
for (int i=pos[j]+1;i<=bnd[j];i++) f[i][j]=1;
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
f[i][j]+=f[i-1][j]+f[i][j-1]-f[i-1][j-1];
int Tot=0;
vector<pa>all;
for (int j=1;j<=n;j++)
for (int i=pos[j]+1;i<=bnd[j];i++)
if (calc(i,j)*2<=tot&&(tot<=100||calc(i,j)*9<=tot)) all.push_back(mp(i,j));
int ooo=rnd()%all.size();
cx=all[ooo].fi,cy=all[ooo].se;
// if (tot>0)
// {
// for (auto u:g)
// {
// sm+=bnd[u]-pos[u];
// if (od<sm)
// {
// cx=bnd[u]-(sm-od)+1;
// cy=u;
// break;
// }
// }
// }
if (ask2(cx,cy)=="<")
{
pos[cy]=cx;
for (int i=n;i>=1;i--)
{
if (i<n)
pos[i]=max(pos[i],pos[i+1]);
if (i!=cy)
geta(i,cx,cy);
}
} else
{
bnd[cy]=cx-1;
for (int i=1;i<=n;i++)
{
if (i>1)
bnd[i]=min(bnd[i],bnd[i-1]);
if (i!=cy)
getb(i,cx,cy);
}
}
return 0;
}
int main(int nn)
{
n=nn;
mx=n,my=n;
if (ask2(n,n)=="<")
{
return n*n;
}
poly g;
for (int i=1;i<=n;i++)
g.push_back(i),bnd[i]=n;
while (!solve());
int ans=0;
for (int i=1;i<=n;i++) ans+=pos[i];
return ans;
}
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 10
Accepted
Test #1:
score: 10
Accepted
time: 0ms
memory: 5820kb
input:
6 3 384 45 837639677
output:
1 26 8
result:
points 1.0 correct, ask1 called 26 time(s), ask2 called 8 time(s)
Test #2:
score: 10
Accepted
time: 1ms
memory: 5832kb
input:
8 59 512 45 439876779
output:
1 53 12
result:
points 1.0 correct, ask1 called 53 time(s), ask2 called 12 time(s)
Test #3:
score: 10
Accepted
time: 1ms
memory: 5880kb
input:
9 27 576 45 777817090
output:
1 48 10
result:
points 1.0 correct, ask1 called 48 time(s), ask2 called 10 time(s)
Test #4:
score: 10
Accepted
time: 1ms
memory: 5824kb
input:
7 14 448 45 42081112
output:
1 11 6
result:
points 1.0 correct, ask1 called 11 time(s), ask2 called 6 time(s)
Test #5:
score: 10
Accepted
time: 1ms
memory: 5820kb
input:
6 14 384 45 380054191
output:
1 23 9
result:
points 1.0 correct, ask1 called 23 time(s), ask2 called 9 time(s)
Test #6:
score: 10
Accepted
time: 1ms
memory: 5836kb
input:
9 13 576 45 718060038
output:
1 48 9
result:
points 1.0 correct, ask1 called 48 time(s), ask2 called 9 time(s)
Test #7:
score: 10
Accepted
time: 0ms
memory: 5840kb
input:
9 16 576 45 1056065885
output:
1 40 8
result:
points 1.0 correct, ask1 called 40 time(s), ask2 called 8 time(s)
Test #8:
score: 10
Accepted
time: 1ms
memory: 5824kb
input:
7 41 448 45 320297139
output:
1 46 9
result:
points 1.0 correct, ask1 called 46 time(s), ask2 called 9 time(s)
Test #9:
score: 10
Accepted
time: 0ms
memory: 5784kb
input:
7 33 448 45 658302986
output:
1 56 11
result:
points 1.0 correct, ask1 called 56 time(s), ask2 called 11 time(s)
Test #10:
score: 10
Accepted
time: 1ms
memory: 5832kb
input:
7 30 448 45 996276065
output:
1 55 11
result:
points 1.0 correct, ask1 called 55 time(s), ask2 called 11 time(s)
Test #11:
score: 10
Accepted
time: 1ms
memory: 5760kb
input:
7 37 448 45 598480398
output:
1 29 8
result:
points 1.0 correct, ask1 called 29 time(s), ask2 called 8 time(s)
Test #12:
score: 10
Accepted
time: 1ms
memory: 5836kb
input:
10 27 640 45 936486245
output:
1 69 10
result:
points 1.0 correct, ask1 called 69 time(s), ask2 called 10 time(s)
Test #13:
score: 10
Accepted
time: 1ms
memory: 7860kb
input:
8 22 512 45 200750268
output:
1 50 8
result:
points 1.0 correct, ask1 called 50 time(s), ask2 called 8 time(s)
Test #14:
score: 10
Accepted
time: 1ms
memory: 5836kb
input:
10 41 640 45 538723346
output:
1 69 9
result:
points 1.0 correct, ask1 called 69 time(s), ask2 called 9 time(s)
Test #15:
score: 10
Accepted
time: 1ms
memory: 5904kb
input:
6 35 384 45 876729193
output:
1 30 6
result:
points 1.0 correct, ask1 called 30 time(s), ask2 called 6 time(s)
Test #16:
score: 10
Accepted
time: 1ms
memory: 5888kb
input:
10 98 640 45 140960448
output:
1 66 13
result:
points 1.0 correct, ask1 called 66 time(s), ask2 called 13 time(s)
Test #17:
score: 10
Accepted
time: 1ms
memory: 7868kb
input:
8 36 512 45 478966295
output:
1 24 6
result:
points 1.0 correct, ask1 called 24 time(s), ask2 called 6 time(s)
Test #18:
score: 10
Accepted
time: 0ms
memory: 5844kb
input:
8 9 512 45 81170628
output:
1 48 9
result:
points 1.0 correct, ask1 called 48 time(s), ask2 called 9 time(s)
Test #19:
score: 10
Accepted
time: 1ms
memory: 5752kb
input:
6 20 384 45 419176475
output:
1 21 8
result:
points 1.0 correct, ask1 called 21 time(s), ask2 called 8 time(s)
Test #20:
score: 10
Accepted
time: 1ms
memory: 5756kb
input:
6 23 384 45 757149553
output:
1 22 5
result:
points 1.0 correct, ask1 called 22 time(s), ask2 called 5 time(s)
Subtask #2:
score: 0
Wrong Answer
Test #21:
score: 20
Acceptable Answer
time: 952ms
memory: 52684kb
input:
1998 997469 511488 45 691176210
output:
1 67786 40
result:
points 0.22222222220 correct, ask1 called 67786 time(s), ask2 called 40 time(s)
Test #22:
score: 40
Acceptable Answer
time: 847ms
memory: 52688kb
input:
1997 250682 511232 45 1029182057
output:
1 47513 37
result:
points 0.44444444440 correct, ask1 called 47513 time(s), ask2 called 37 time(s)
Test #23:
score: 20
Acceptable Answer
time: 974ms
memory: 52692kb
input:
2000 1742216 512000 45 293413312
output:
1 69331 41
result:
points 0.22222222220 correct, ask1 called 69331 time(s), ask2 called 41 time(s)
Test #24:
score: 90
Accepted
time: 761ms
memory: 52640kb
input:
1996 2394420 510976 45 631419158
output:
1 45839 30
result:
points 1.0 correct, ask1 called 45839 time(s), ask2 called 30 time(s)
Test #25:
score: 90
Accepted
time: 762ms
memory: 52644kb
input:
1998 3398507 511488 45 969425005
output:
1 35447 30
result:
points 1.0 correct, ask1 called 35447 time(s), ask2 called 30 time(s)
Test #26:
score: 0
Wrong Answer
time: 1141ms
memory: 52664kb
input:
1998 574252 511488 45 571662106
output:
1 88101 51
result:
points 0.0 correct, ask1 called 88101 time(s), ask2 called 51 time(s)