답안 #618676

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
618676	2022-08-02T06:36:36 Z	maomao90	Minerals (JOI19_minerals)	C++17	40 / 100	787 ms	4072 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 = 43005;

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

void dnc(vi fi, vi se) {
    assert(SZ(fi) == SZ(se));
    cerr << "fi:";
    for (int i : fi) {
        cerr << ' ' << i;
    }
    cerr << '\n';
    cerr << "se:";
    for (int i : se) {
        cerr << ' ' << i;
    }
    cerr << '\n';
    if (SZ(fi) == 1) {
        Answer(fi[0], se[0]);
        return;
    }
    vi lfi, rfi;
    vector<bool> inlfi(2 * n + 1, 0);
    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;
    REP (i, 1, 2 * n + 1) {
        if (inlfi[i] ^ state[i]) {
            cur = Query(i);
            state[i] ^= 1;
        }
    }
    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	1 ms	208 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct

Subtask #2
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	7 ms	336 KB	Output is correct
2	Correct	13 ms	464 KB	Output is correct
3	Correct	66 ms	592 KB	Output is correct
4	Correct	267 ms	848 KB	Output is correct
5	Correct	774 ms	1492 KB	Output is correct

Subtask #3
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	1 ms	208 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	7 ms	336 KB	Output is correct
6	Correct	13 ms	464 KB	Output is correct
7	Correct	66 ms	592 KB	Output is correct
8	Correct	267 ms	848 KB	Output is correct
9	Correct	774 ms	1492 KB	Output is correct
10	Correct	4 ms	336 KB	Output is correct
11	Correct	324 ms	1136 KB	Output is correct
12	Correct	760 ms	1600 KB	Output is correct
13	Correct	740 ms	1540 KB	Output is correct
14	Correct	787 ms	1312 KB	Output is correct

Subtask #4
0 / 30.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	1 ms	208 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	7 ms	336 KB	Output is correct
6	Correct	13 ms	464 KB	Output is correct
7	Correct	66 ms	592 KB	Output is correct
8	Correct	267 ms	848 KB	Output is correct
9	Correct	774 ms	1492 KB	Output is correct
10	Correct	4 ms	336 KB	Output is correct
11	Correct	324 ms	1136 KB	Output is correct
12	Correct	760 ms	1600 KB	Output is correct
13	Correct	740 ms	1540 KB	Output is correct
14	Correct	787 ms	1312 KB	Output is correct
15	Runtime error	18 ms	4072 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-

Subtask #5
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	1 ms	208 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	7 ms	336 KB	Output is correct
6	Correct	13 ms	464 KB	Output is correct
7	Correct	66 ms	592 KB	Output is correct
8	Correct	267 ms	848 KB	Output is correct
9	Correct	774 ms	1492 KB	Output is correct
10	Correct	4 ms	336 KB	Output is correct
11	Correct	324 ms	1136 KB	Output is correct
12	Correct	760 ms	1600 KB	Output is correct
13	Correct	740 ms	1540 KB	Output is correct
14	Correct	787 ms	1312 KB	Output is correct
15	Runtime error	18 ms	4072 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	1 ms	208 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	7 ms	336 KB	Output is correct
6	Correct	13 ms	464 KB	Output is correct
7	Correct	66 ms	592 KB	Output is correct
8	Correct	267 ms	848 KB	Output is correct
9	Correct	774 ms	1492 KB	Output is correct
10	Correct	4 ms	336 KB	Output is correct
11	Correct	324 ms	1136 KB	Output is correct
12	Correct	760 ms	1600 KB	Output is correct
13	Correct	740 ms	1540 KB	Output is correct
14	Correct	787 ms	1312 KB	Output is correct
15	Runtime error	18 ms	4072 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-

Subtask #7
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	1 ms	208 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	7 ms	336 KB	Output is correct
6	Correct	13 ms	464 KB	Output is correct
7	Correct	66 ms	592 KB	Output is correct
8	Correct	267 ms	848 KB	Output is correct
9	Correct	774 ms	1492 KB	Output is correct
10	Correct	4 ms	336 KB	Output is correct
11	Correct	324 ms	1136 KB	Output is correct
12	Correct	760 ms	1600 KB	Output is correct
13	Correct	740 ms	1540 KB	Output is correct
14	Correct	787 ms	1312 KB	Output is correct
15	Runtime error	18 ms	4072 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-

Subtask #8
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	1 ms	208 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	7 ms	336 KB	Output is correct
6	Correct	13 ms	464 KB	Output is correct
7	Correct	66 ms	592 KB	Output is correct
8	Correct	267 ms	848 KB	Output is correct
9	Correct	774 ms	1492 KB	Output is correct
10	Correct	4 ms	336 KB	Output is correct
11	Correct	324 ms	1136 KB	Output is correct
12	Correct	760 ms	1600 KB	Output is correct
13	Correct	740 ms	1540 KB	Output is correct
14	Correct	787 ms	1312 KB	Output is correct
15	Runtime error	18 ms	4072 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	208 KB	Output is correct
2	Correct	1 ms	208 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	7 ms	336 KB	Output is correct
6	Correct	13 ms	464 KB	Output is correct
7	Correct	66 ms	592 KB	Output is correct
8	Correct	267 ms	848 KB	Output is correct
9	Correct	774 ms	1492 KB	Output is correct
10	Correct	4 ms	336 KB	Output is correct
11	Correct	324 ms	1136 KB	Output is correct
12	Correct	760 ms	1600 KB	Output is correct
13	Correct	740 ms	1540 KB	Output is correct
14	Correct	787 ms	1312 KB	Output is correct
15	Runtime error	18 ms	4072 KB	Execution killed with signal 11
16	Halted	0 ms	0 KB	-

답안 #618676

Compilation message