QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#182888#5375. SearchLynkcat#10 380ms50152kbC++202.6kb2023-09-18 18:05:192024-07-04 02:02:20

Judging History

你现在查看的是最新测评结果

  • [2024-07-04 02:02:20]
  • 评测
  • 测评结果：10
  • 用时：380ms
  • 内存：50152kb
查看
  • [2023-09-18 18:05:19]
  • 提交

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(2006100920070217);
    void geta(int k,int x,int y,int rb)
    {
        if (!x) return;
        int l=pos[k]+1,r=rb;
        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=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=rnd()%g.size();
        // md=0;
        int mid=g[md];
        // 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;
                // cout<<"!!!"<<u<<" "<<pos[u]<<endl;
                if (cx>n||ask1(cx,cy,pos[u]+1,u)==">") 
                {
                    if (cx<=n) upd(u,cx,cy);
                    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;
    }
}
源文件, 语言: C++20

詳細信息

Subtask #1:

score: 10
Accepted

Test #1:

score: 10
Accepted
time: 1ms
memory: 4068kb

input:

6 3
384 45
837639677

output:

1 12 3

result:

points 1.0 correct, ask1 called 12 time(s), ask2 called 3 time(s)

Test #2:

score: 10
Accepted
time: 1ms
memory: 3824kb

input:

8 59
512 45
439876779

output:

1 75 9

result:

points 1.0 correct, ask1 called 75 time(s), ask2 called 9 time(s)

Test #3:

score: 10
Accepted
time: 1ms
memory: 4116kb

input:

9 27
576 45
777817090

output:

1 58 7

result:

points 1.0 correct, ask1 called 58 time(s), ask2 called 7 time(s)

Test #4:

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

input:

7 14
448 45
42081112

output:

1 18 8

result:

points 1.0 correct, ask1 called 18 time(s), ask2 called 8 time(s)

Test #5:

score: 10
Accepted
time: 1ms
memory: 3916kb

input:

6 14
384 45
380054191

output:

1 10 3

result:

points 1.0 correct, ask1 called 10 time(s), ask2 called 3 time(s)

Test #6:

score: 10
Accepted
time: 0ms
memory: 3832kb

input:

9 13
576 45
718060038

output:

1 31 6

result:

points 1.0 correct, ask1 called 31 time(s), ask2 called 6 time(s)

Test #7:

score: 10
Accepted
time: 0ms
memory: 3912kb

input:

9 16
576 45
1056065885

output:

1 66 9

result:

points 1.0 correct, ask1 called 66 time(s), ask2 called 9 time(s)

Test #8:

score: 10
Accepted
time: 0ms
memory: 3844kb

input:

7 41
448 45
320297139

output:

1 24 7

result:

points 1.0 correct, ask1 called 24 time(s), ask2 called 7 time(s)

Test #9:

score: 10
Accepted
time: 0ms
memory: 3776kb

input:

7 33
448 45
658302986

output:

1 26 9

result:

points 1.0 correct, ask1 called 26 time(s), ask2 called 9 time(s)

Test #10:

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

input:

7 30
448 45
996276065

output:

1 30 7

result:

points 1.0 correct, ask1 called 30 time(s), ask2 called 7 time(s)

Test #11:

score: 10
Accepted
time: 0ms
memory: 3816kb

input:

7 37
448 45
598480398

output:

1 21 8

result:

points 1.0 correct, ask1 called 21 time(s), ask2 called 8 time(s)

Test #12:

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

input:

10 27
640 45
936486245

output:

1 80 9

result:

points 1.0 correct, ask1 called 80 time(s), ask2 called 9 time(s)

Test #13:

score: 10
Accepted
time: 0ms
memory: 3852kb

input:

8 22
512 45
200750268

output:

1 63 10

result:

points 1.0 correct, ask1 called 63 time(s), ask2 called 10 time(s)

Test #14:

score: 10
Accepted
time: 0ms
memory: 3832kb

input:

10 41
640 45
538723346

output:

1 64 9

result:

points 1.0 correct, ask1 called 64 time(s), ask2 called 9 time(s)

Test #15:

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

input:

6 35
384 45
876729193

output:

1 19 5

result:

points 1.0 correct, ask1 called 19 time(s), ask2 called 5 time(s)

Test #16:

score: 10
Accepted
time: 0ms
memory: 3864kb

input:

10 98
640 45
140960448

output:

1 78 9

result:

points 1.0 correct, ask1 called 78 time(s), ask2 called 9 time(s)

Test #17:

score: 10
Accepted
time: 0ms
memory: 3856kb

input:

8 36
512 45
478966295

output:

1 65 8

result:

points 1.0 correct, ask1 called 65 time(s), ask2 called 8 time(s)

Test #18:

score: 10
Accepted
time: 0ms
memory: 3916kb

input:

8 9
512 45
81170628

output:

1 80 10

result:

points 1.0 correct, ask1 called 80 time(s), ask2 called 10 time(s)

Test #19:

score: 10
Accepted
time: 0ms
memory: 3812kb

input:

6 20
384 45
419176475

output:

1 26 8

result:

points 1.0 correct, ask1 called 26 time(s), ask2 called 8 time(s)

Test #20:

score: 10
Accepted
time: 0ms
memory: 3772kb

input:

6 23
384 45
757149553

output:

1 14 5

result:

points 1.0 correct, ask1 called 14 time(s), ask2 called 5 time(s)

Subtask #2:

score: 0
Wrong Answer

Test #21:

score: 20
Acceptable Answer
time: 375ms
memory: 50084kb

input:

1998 997469
511488 45
691176210

output:

1 24949 40

result:

points 0.22222222220 correct, ask1 called 24949 time(s), ask2 called 40 time(s)

Test #22:

score: 20
Acceptable Answer
time: 365ms
memory: 49928kb

input:

1997 250682
511232 45
1029182057

output:

1 58286 43

result:

points 0.22222222220 correct, ask1 called 58286 time(s), ask2 called 43 time(s)

Test #23:

score: 20
Acceptable Answer
time: 364ms
memory: 50152kb

input:

2000 1742216
512000 45
293413312

output:

1 42219 39

result:

points 0.22222222220 correct, ask1 called 42219 time(s), ask2 called 39 time(s)

Test #24:

score: 0
Wrong Answer
time: 380ms
memory: 49872kb

input:

1996 2394420
510976 45
631419158

output:

1 23548 75

result:

points 0.0 correct, ask1 called 23548 time(s), ask2 called 75 time(s)
English 繁體中文 简体中文

伺服器時間: 2024-12-02 18:43:49 | 開源專案