QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #182897 | #5375. Search | Lynkcat | 10 | 368ms | 50364kb | C++20 | 3.3kb | 2023-09-18 18:39:43 | 2023-09-18 18:39:43 |
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 n;
int bnd[N],pos[N];
mt19937_64 rnd(time(0));
void geta(int k,int x,int y,int rb)
{
if (!x) return;
int l=pos[k]+1,r=min(rb,bnd[k]);
while (l<=r)
{
int mid=l+(r-l)/2;
if (ask1(mid,k,x,y)=="<")
{
pos[k]=mid;
l=mid+1;
} else r=mid-1;
}
}
void getr(int k)
{
int l=pos[k]+1,r=bnd[k];
while (l<=r)
{
int mid=l+(r-l)/2;
if (ask2(mid,k)=="<")
{
pos[k]=mid;
l=mid+1;
} else r=mid-1;
}
}
void upd(int k,int x,int y)
{
int l=max(1,pos[k]+1),r=bnd[k];
while (l<=r)
{
int mid=l+(r-l)/2;
if (ask1(mid,k,x,y)=="<")
{
l=mid+1;
} else
{
bnd[k]=mid-1;
r=mid-1;
}
}
}
void solve(poly g)
{
if (g.empty()) return;
int md=0;
// for (int i=0;i<g.size();i++)
// {
// int u=g[i];
// if (i==md) continue;
// if (ask1(pos[u]+1,u,pos[g[md]]+1,g[md])=="<") md=i;
// }
md=rnd()%g.size();
// if (g.size()>100) md=g.size()-rnd()%50-1;
// md=0;
int mid=g[md];
// cout<<mid<<" "<<pos[mid]+1<<" "<<bnd[mid]<<endl;
// for (auto u:g) cout<<u<<",";
// cout<<endl;
getr(mid);
// cout<<mid<<" "<<pos[mid]<<endl;
int lst=n;
for (auto u:g)
if (u!=mid)
{
geta(u,pos[mid],mid,lst);
lst=pos[u];
}
// for (auto u:g) cout<<u<<":"<<pos[u]<<endl;
// cout<<"_--------------"<<endl;
int cx=pos[mid],cy=mid;
cx++;
poly lf;
for (auto u:g)
if (u!=mid)
{
if (pos[u]==n) continue;
if (cx>n||ask1(cx,cy,pos[u]+1,u)==">")
{
if (pos[u]+1>bnd[u])
{
cx=pos[u]+1,cy=u;
}
}
}
for (auto u:g)
if (u!=mid)
{
if (pos[u]==n) continue;
if (cx>n||ask1(cx,cy,pos[u]+1,u)==">")
{
if (cx<=n) upd(u,cx,cy);
if (pos[u]+1>bnd[u]) continue;
lf.push_back(u);
}
}
solve(lf);
}
int main(int nn)
{
n=nn;
poly g;
for (int i=1;i<=n;i++)
g.push_back(i),bnd[i]=n;
solve(g);
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: 3884kb
input:
6 3 384 45 837639677
output:
1 51 9
result:
points 1.0 correct, ask1 called 51 time(s), ask2 called 9 time(s)
Test #2:
score: 10
Accepted
time: 1ms
memory: 4168kb
input:
8 59 512 45 439876779
output:
1 52 9
result:
points 1.0 correct, ask1 called 52 time(s), ask2 called 9 time(s)
Test #3:
score: 10
Accepted
time: 0ms
memory: 4140kb
input:
9 27 576 45 777817090
output:
1 57 7
result:
points 1.0 correct, ask1 called 57 time(s), ask2 called 7 time(s)
Test #4:
score: 10
Accepted
time: 0ms
memory: 3908kb
input:
7 14 448 45 42081112
output:
1 52 11
result:
points 1.0 correct, ask1 called 52 time(s), ask2 called 11 time(s)
Test #5:
score: 10
Accepted
time: 1ms
memory: 4140kb
input:
6 14 384 45 380054191
output:
1 44 9
result:
points 1.0 correct, ask1 called 44 time(s), ask2 called 9 time(s)
Test #6:
score: 10
Accepted
time: 0ms
memory: 3976kb
input:
9 13 576 45 718060038
output:
1 40 9
result:
points 1.0 correct, ask1 called 40 time(s), ask2 called 9 time(s)
Test #7:
score: 10
Accepted
time: 0ms
memory: 4120kb
input:
9 16 576 45 1056065885
output:
1 61 9
result:
points 1.0 correct, ask1 called 61 time(s), ask2 called 9 time(s)
Test #8:
score: 10
Accepted
time: 0ms
memory: 4164kb
input:
7 41 448 45 320297139
output:
1 53 11
result:
points 1.0 correct, ask1 called 53 time(s), ask2 called 11 time(s)
Test #9:
score: 10
Accepted
time: 0ms
memory: 3880kb
input:
7 33 448 45 658302986
output:
1 52 9
result:
points 1.0 correct, ask1 called 52 time(s), ask2 called 9 time(s)
Test #10:
score: 10
Accepted
time: 1ms
memory: 6200kb
input:
7 30 448 45 996276065
output:
1 49 7
result:
points 1.0 correct, ask1 called 49 time(s), ask2 called 7 time(s)
Test #11:
score: 10
Accepted
time: 0ms
memory: 3980kb
input:
7 37 448 45 598480398
output:
1 18 3
result:
points 1.0 correct, ask1 called 18 time(s), ask2 called 3 time(s)
Test #12:
score: 10
Accepted
time: 0ms
memory: 3892kb
input:
10 27 640 45 936486245
output:
1 43 6
result:
points 1.0 correct, ask1 called 43 time(s), ask2 called 6 time(s)
Test #13:
score: 10
Accepted
time: 0ms
memory: 3920kb
input:
8 22 512 45 200750268
output:
1 34 6
result:
points 1.0 correct, ask1 called 34 time(s), ask2 called 6 time(s)
Test #14:
score: 10
Accepted
time: 0ms
memory: 3924kb
input:
10 41 640 45 538723346
output:
1 55 8
result:
points 1.0 correct, ask1 called 55 time(s), ask2 called 8 time(s)
Test #15:
score: 10
Accepted
time: 0ms
memory: 3836kb
input:
6 35 384 45 876729193
output:
1 43 7
result:
points 1.0 correct, ask1 called 43 time(s), ask2 called 7 time(s)
Test #16:
score: 10
Accepted
time: 0ms
memory: 3976kb
input:
10 98 640 45 140960448
output:
1 76 14
result:
points 1.0 correct, ask1 called 76 time(s), ask2 called 14 time(s)
Test #17:
score: 10
Accepted
time: 0ms
memory: 3852kb
input:
8 36 512 45 478966295
output:
1 40 6
result:
points 1.0 correct, ask1 called 40 time(s), ask2 called 6 time(s)
Test #18:
score: 10
Accepted
time: 0ms
memory: 3832kb
input:
8 9 512 45 81170628
output:
1 63 8
result:
points 1.0 correct, ask1 called 63 time(s), ask2 called 8 time(s)
Test #19:
score: 10
Accepted
time: 1ms
memory: 5988kb
input:
6 20 384 45 419176475
output:
1 41 7
result:
points 1.0 correct, ask1 called 41 time(s), ask2 called 7 time(s)
Test #20:
score: 10
Accepted
time: 0ms
memory: 3904kb
input:
6 23 384 45 757149553
output:
1 53 6
result:
points 1.0 correct, ask1 called 53 time(s), ask2 called 6 time(s)
Subtask #2:
score: 0
Wrong Answer
Test #21:
score: 0
Wrong Answer
time: 368ms
memory: 50364kb
input:
1998 997469 511488 45 691176210
output:
1 38754 71
result:
points 0.0 correct, ask1 called 38754 time(s), ask2 called 71 time(s)