답안 #618690

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
618690	2022-08-02T06:42:19 Z	maomao90	Minerals (JOI19_minerals)	C++17	40 / 100	36 ms	2648 KB

minerals

// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h> 
#include "minerals.h"
using namespace std;

#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;

#ifndef DEBUG
#define cerr if (0) cerr
#endif

const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 86005;

int n;
vi lft, rht;
bool state[MAXN];

bool inlfi[MAXN];
void dnc(vi &fi, vi &se) {
    assert(SZ(fi) == SZ(se));
    if (SZ(fi) == 1) {
        Answer(fi[0], se[0]);
        return;
    }
    vi lfi, rfi;
    REP (i, 0, SZ(fi) / 2) {
        lfi.pb(fi[i]);
        inlfi[fi[i]] = 1;
    }
    REP (i, SZ(fi) / 2, SZ(se)) {
        rfi.pb(fi[i]);
    }
    int cur = -1;
    for (int i : fi) {
        if (inlfi[i] ^ state[i]) {
            cur = Query(i);
            state[i] ^= 1;
        }
    }
    for (int i : lfi) {
        inlfi[i] = 0;
    }
    assert(cur != -1);
    vi lse, rse;
    for (int i : se) {
        int nxt = Query(i);
        if (nxt == cur) {
            lse.pb(i);
        } else {
            rse.pb(i);
        }
        cur = nxt;
    }
    dnc(lfi, lse);
    dnc(rfi, rse);
}

void Solve(int N) {
    n = N;
    int cur = 0;
    REP (i, 1, 2 * n + 1) {
        int nxt = Query(i);
        if (nxt > cur) {
            lft.pb(i);
        } else {
            rht.pb(i);
        }
        cur = nxt;
    }
    assert(SZ(lft) == n);
    REP (i, 1, 2 * n + 1) {
        Query(i);
    }
    dnc(lft, rht);
}

Subtask #1
6.0 / 6.0

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

Subtask #2
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	2 ms	336 KB	Output is correct
3	Correct	4 ms	592 KB	Output is correct
4	Correct	8 ms	720 KB	Output is correct
5	Correct	14 ms	1060 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	0 ms	208 KB	Output is correct
3	Correct	1 ms	208 KB	Output is correct
4	Correct	1 ms	208 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	2 ms	336 KB	Output is correct
7	Correct	4 ms	592 KB	Output is correct
8	Correct	8 ms	720 KB	Output is correct
9	Correct	14 ms	1060 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct
11	Correct	9 ms	976 KB	Output is correct
12	Correct	13 ms	1204 KB	Output is correct
13	Correct	11 ms	1160 KB	Output is correct
14	Correct	12 ms	1104 KB	Output is correct

Subtask #4
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	0 ms	208 KB	Output is correct
3	Correct	1 ms	208 KB	Output is correct
4	Correct	1 ms	208 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	2 ms	336 KB	Output is correct
7	Correct	4 ms	592 KB	Output is correct
8	Correct	8 ms	720 KB	Output is correct
9	Correct	14 ms	1060 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct
11	Correct	9 ms	976 KB	Output is correct
12	Correct	13 ms	1204 KB	Output is correct
13	Correct	11 ms	1160 KB	Output is correct
14	Correct	12 ms	1104 KB	Output is correct
15	Incorrect	36 ms	2648 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #5
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	0 ms	208 KB	Output is correct
3	Correct	1 ms	208 KB	Output is correct
4	Correct	1 ms	208 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	2 ms	336 KB	Output is correct
7	Correct	4 ms	592 KB	Output is correct
8	Correct	8 ms	720 KB	Output is correct
9	Correct	14 ms	1060 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct
11	Correct	9 ms	976 KB	Output is correct
12	Correct	13 ms	1204 KB	Output is correct
13	Correct	11 ms	1160 KB	Output is correct
14	Correct	12 ms	1104 KB	Output is correct
15	Incorrect	36 ms	2648 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	0 ms	208 KB	Output is correct
3	Correct	1 ms	208 KB	Output is correct
4	Correct	1 ms	208 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	2 ms	336 KB	Output is correct
7	Correct	4 ms	592 KB	Output is correct
8	Correct	8 ms	720 KB	Output is correct
9	Correct	14 ms	1060 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct
11	Correct	9 ms	976 KB	Output is correct
12	Correct	13 ms	1204 KB	Output is correct
13	Correct	11 ms	1160 KB	Output is correct
14	Correct	12 ms	1104 KB	Output is correct
15	Incorrect	36 ms	2648 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #7
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	0 ms	208 KB	Output is correct
3	Correct	1 ms	208 KB	Output is correct
4	Correct	1 ms	208 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	2 ms	336 KB	Output is correct
7	Correct	4 ms	592 KB	Output is correct
8	Correct	8 ms	720 KB	Output is correct
9	Correct	14 ms	1060 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct
11	Correct	9 ms	976 KB	Output is correct
12	Correct	13 ms	1204 KB	Output is correct
13	Correct	11 ms	1160 KB	Output is correct
14	Correct	12 ms	1104 KB	Output is correct
15	Incorrect	36 ms	2648 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #8
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	0 ms	208 KB	Output is correct
3	Correct	1 ms	208 KB	Output is correct
4	Correct	1 ms	208 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	2 ms	336 KB	Output is correct
7	Correct	4 ms	592 KB	Output is correct
8	Correct	8 ms	720 KB	Output is correct
9	Correct	14 ms	1060 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct
11	Correct	9 ms	976 KB	Output is correct
12	Correct	13 ms	1204 KB	Output is correct
13	Correct	11 ms	1160 KB	Output is correct
14	Correct	12 ms	1104 KB	Output is correct
15	Incorrect	36 ms	2648 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	0 ms	208 KB	Output is correct
3	Correct	1 ms	208 KB	Output is correct
4	Correct	1 ms	208 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	2 ms	336 KB	Output is correct
7	Correct	4 ms	592 KB	Output is correct
8	Correct	8 ms	720 KB	Output is correct
9	Correct	14 ms	1060 KB	Output is correct
10	Correct	1 ms	336 KB	Output is correct
11	Correct	9 ms	976 KB	Output is correct
12	Correct	13 ms	1204 KB	Output is correct
13	Correct	11 ms	1160 KB	Output is correct
14	Correct	12 ms	1104 KB	Output is correct
15	Incorrect	36 ms	2648 KB	Wrong Answer [2]
16	Halted	0 ms	0 KB	-

답안 #618690

Compilation message