답안 #915479

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
915479	2024-01-24T03:14:39 Z	guagua0407	Minerals (JOI19_minerals)	C++17	40 / 100	28 ms	3132 KB

minerals

#include "minerals.h"
#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second

vector<int> a;
vector<int> belong;
vector<pair<int,int>> vec;

void go(int l,int r,vector<int> &b,int id){
    if(l==r){
        //Query(a[l]);
        assert((int)b.size()==1);
        vec.push_back({a[l],b[0]});
        return;
    }
    int mid=min(r-1,(l+r+50)/2);
    int cur=0;
    for(int i=mid+1;i<=r;i++){
        cur=Query(a[i]);
    }
    vector<int> ls,rs;
    for(auto v:b){
        if(belong[v]<=mid){
            ls.push_back(v);
            continue;
        }
        if((int)ls.size()==mid-l+1){
            rs.push_back(v);
            continue;
        }
        if((int)rs.size()==r-mid){
            ls.push_back(v);
            continue;
        }
        int x=Query(v);
        if(id==0){
            if(x!=cur){
                ls.push_back(v);
            }
            else{
                rs.push_back(v);
            }
        }
        else{
            if(x==cur){
                ls.push_back(v);
            }
            else{
                rs.push_back(v);
            }
        }
        cur=x;
    }
    vector<int>().swap(b);
    if(id==0){
        go(l,mid,ls,0);
        go(mid+1,r,rs,1);
    }
    else{
        go(l,mid,ls,1);
        go(mid+1,r,rs,0);
    }
}

void Solve(int n){
    vector<bool> ok(2*n+1);
    int prv=0;
    vector<int> ord(2*n+1);
    for(int i=1;i<=2*n;i++){
        ord[i]=i;
    }
    mt19937 rng(time(NULL));
    shuffle(ord.begin()+1,ord.end(),rng);
    for(int t=1;t<=2*n;t++){
        int i=ord[t];
        int x=Query(i);
        if(x==prv+1){
            ok[i]=true;
        }
        prv=x;
    }
    vector<int> b;
    int cnt=-1;
    belong.resize(2*n+1);
    for(int t=1;t<=2*n;t++){
        int i=ord[t];
        if(ok[i]){
            a.push_back(i);
            cnt++;
        }
        else{
            b.push_back(i);
            belong[i]=cnt;
        }
    }
    go(0,n-1,b,1);
    for(auto v:vec){
        Answer(v.f,v.s);
    }
}

Subtask #1
6.0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	588 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct

Subtask #2
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	596 KB	Output is correct
2	Correct	2 ms	584 KB	Output is correct
3	Correct	3 ms	600 KB	Output is correct
4	Correct	6 ms	856 KB	Output is correct
5	Correct	11 ms	1324 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	588 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	1 ms	596 KB	Output is correct
6	Correct	2 ms	584 KB	Output is correct
7	Correct	3 ms	600 KB	Output is correct
8	Correct	6 ms	856 KB	Output is correct
9	Correct	11 ms	1324 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	7 ms	1112 KB	Output is correct
12	Correct	12 ms	1440 KB	Output is correct
13	Correct	11 ms	1624 KB	Output is correct
14	Correct	11 ms	1884 KB	Output is correct

Subtask #4
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	588 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	1 ms	596 KB	Output is correct
6	Correct	2 ms	584 KB	Output is correct
7	Correct	3 ms	600 KB	Output is correct
8	Correct	6 ms	856 KB	Output is correct
9	Correct	11 ms	1324 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	7 ms	1112 KB	Output is correct
12	Correct	12 ms	1440 KB	Output is correct
13	Correct	11 ms	1624 KB	Output is correct
14	Correct	11 ms	1884 KB	Output is correct
15	Incorrect	28 ms	3132 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #5
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	588 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	1 ms	596 KB	Output is correct
6	Correct	2 ms	584 KB	Output is correct
7	Correct	3 ms	600 KB	Output is correct
8	Correct	6 ms	856 KB	Output is correct
9	Correct	11 ms	1324 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	7 ms	1112 KB	Output is correct
12	Correct	12 ms	1440 KB	Output is correct
13	Correct	11 ms	1624 KB	Output is correct
14	Correct	11 ms	1884 KB	Output is correct
15	Incorrect	28 ms	3132 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	588 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	1 ms	596 KB	Output is correct
6	Correct	2 ms	584 KB	Output is correct
7	Correct	3 ms	600 KB	Output is correct
8	Correct	6 ms	856 KB	Output is correct
9	Correct	11 ms	1324 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	7 ms	1112 KB	Output is correct
12	Correct	12 ms	1440 KB	Output is correct
13	Correct	11 ms	1624 KB	Output is correct
14	Correct	11 ms	1884 KB	Output is correct
15	Incorrect	28 ms	3132 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #7
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	588 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	1 ms	596 KB	Output is correct
6	Correct	2 ms	584 KB	Output is correct
7	Correct	3 ms	600 KB	Output is correct
8	Correct	6 ms	856 KB	Output is correct
9	Correct	11 ms	1324 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	7 ms	1112 KB	Output is correct
12	Correct	12 ms	1440 KB	Output is correct
13	Correct	11 ms	1624 KB	Output is correct
14	Correct	11 ms	1884 KB	Output is correct
15	Incorrect	28 ms	3132 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #8
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	588 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	1 ms	596 KB	Output is correct
6	Correct	2 ms	584 KB	Output is correct
7	Correct	3 ms	600 KB	Output is correct
8	Correct	6 ms	856 KB	Output is correct
9	Correct	11 ms	1324 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	7 ms	1112 KB	Output is correct
12	Correct	12 ms	1440 KB	Output is correct
13	Correct	11 ms	1624 KB	Output is correct
14	Correct	11 ms	1884 KB	Output is correct
15	Incorrect	28 ms	3132 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	588 KB	Output is correct
2	Correct	0 ms	344 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	1 ms	596 KB	Output is correct
6	Correct	2 ms	584 KB	Output is correct
7	Correct	3 ms	600 KB	Output is correct
8	Correct	6 ms	856 KB	Output is correct
9	Correct	11 ms	1324 KB	Output is correct
10	Correct	1 ms	344 KB	Output is correct
11	Correct	7 ms	1112 KB	Output is correct
12	Correct	12 ms	1440 KB	Output is correct
13	Correct	11 ms	1624 KB	Output is correct
14	Correct	11 ms	1884 KB	Output is correct
15	Incorrect	28 ms	3132 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

답안 #915479

Compilation message