답안 #335518

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
335518	2020-12-13T00:16:26 Z	rocks03	Minerals (JOI19_minerals)	C++14	40 / 100	43 ms	2908 KB

minerals

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ff first
#define ss second
#define pb push_back
#define SZ(x) ((int)(x).size())
#define all(x) x.begin(), x.end()
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int Query(int x);
void Answer(int a, int b);

vector<pii> risposta;
int already;
void dc(vector<int>& a, vector<int>& b){
    assert(SZ(a) == SZ(b));
    if(SZ(a) == 0) return;
    if(SZ(a) == 1){
        already += 1;
        //Query(a[0]);
        risposta.pb({a[0], b[0]});
        return;
    }
    int m = SZ(b) / 2, prev = already + SZ(a);
    for(int i = 0; i < m; i++){
        Query(b[i]);
    }
    vector<int> b_left, b_right;
    for(int i = 0; i < SZ(a); i++){
        int ans = Query(a[i]);
        if(ans < prev){
            b_right.pb(a[i]);
        } else if(ans == prev){
            b_left.pb(a[i]);
        }
        prev = ans;
    }
    vector<int> a_left, a_right;
    for(int i = 0; i < m; i++){
        a_left.pb(b[i]);
    }
    dc(a_left, b_left);
    for(int i = m; i < SZ(b); i++){
        Query(b[i]);
        a_right.pb(b[i]);
    }
    dc(a_right, b_right);
}

void Solve(int N){
    vector<int> a, b;
    int prev = 0;
    vector<int> v(2 * N);
    iota(all(v), 1);
    shuffle(all(v), rng);
    for(int i = 0; i < 2 * N; i++){
        int ans = Query(v[i]);
        if(ans == prev){
            Query(v[i]);
            b.pb(v[i]);
        } else if(ans > prev){
            a.pb(v[i]);
        }
        prev = ans;
        if(ans == N){
            i++;
            while(i < 2 * N){
                b.pb(v[i++]);
            }
            break;
        }
    }
    dc(a, b);
    for(auto x : risposta){
        Answer(x.ff, x.ss);
    }
}

Subtask #1
6.0 / 6.0

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

Subtask #2
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	2 ms	512 KB	Output is correct
3	Correct	5 ms	620 KB	Output is correct
4	Correct	9 ms	876 KB	Output is correct
5	Correct	18 ms	1516 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	2 ms	512 KB	Output is correct
7	Correct	5 ms	620 KB	Output is correct
8	Correct	9 ms	876 KB	Output is correct
9	Correct	18 ms	1516 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	12 ms	1132 KB	Output is correct
12	Correct	18 ms	1536 KB	Output is correct
13	Correct	17 ms	1516 KB	Output is correct
14	Correct	19 ms	1388 KB	Output is correct

Subtask #4
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	2 ms	512 KB	Output is correct
7	Correct	5 ms	620 KB	Output is correct
8	Correct	9 ms	876 KB	Output is correct
9	Correct	18 ms	1516 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	12 ms	1132 KB	Output is correct
12	Correct	18 ms	1536 KB	Output is correct
13	Correct	17 ms	1516 KB	Output is correct
14	Correct	19 ms	1388 KB	Output is correct
15	Incorrect	43 ms	2908 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #5
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	2 ms	512 KB	Output is correct
7	Correct	5 ms	620 KB	Output is correct
8	Correct	9 ms	876 KB	Output is correct
9	Correct	18 ms	1516 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	12 ms	1132 KB	Output is correct
12	Correct	18 ms	1536 KB	Output is correct
13	Correct	17 ms	1516 KB	Output is correct
14	Correct	19 ms	1388 KB	Output is correct
15	Incorrect	43 ms	2908 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	2 ms	512 KB	Output is correct
7	Correct	5 ms	620 KB	Output is correct
8	Correct	9 ms	876 KB	Output is correct
9	Correct	18 ms	1516 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	12 ms	1132 KB	Output is correct
12	Correct	18 ms	1536 KB	Output is correct
13	Correct	17 ms	1516 KB	Output is correct
14	Correct	19 ms	1388 KB	Output is correct
15	Incorrect	43 ms	2908 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #7
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	2 ms	512 KB	Output is correct
7	Correct	5 ms	620 KB	Output is correct
8	Correct	9 ms	876 KB	Output is correct
9	Correct	18 ms	1516 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	12 ms	1132 KB	Output is correct
12	Correct	18 ms	1536 KB	Output is correct
13	Correct	17 ms	1516 KB	Output is correct
14	Correct	19 ms	1388 KB	Output is correct
15	Incorrect	43 ms	2908 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #8
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	2 ms	512 KB	Output is correct
7	Correct	5 ms	620 KB	Output is correct
8	Correct	9 ms	876 KB	Output is correct
9	Correct	18 ms	1516 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	12 ms	1132 KB	Output is correct
12	Correct	18 ms	1536 KB	Output is correct
13	Correct	17 ms	1516 KB	Output is correct
14	Correct	19 ms	1388 KB	Output is correct
15	Incorrect	43 ms	2908 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	2 ms	512 KB	Output is correct
7	Correct	5 ms	620 KB	Output is correct
8	Correct	9 ms	876 KB	Output is correct
9	Correct	18 ms	1516 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	12 ms	1132 KB	Output is correct
12	Correct	18 ms	1536 KB	Output is correct
13	Correct	17 ms	1516 KB	Output is correct
14	Correct	19 ms	1388 KB	Output is correct
15	Incorrect	43 ms	2908 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

답안 #335518

Compilation message