oj.uz

Submission #120639

# Submission time Handle Problem Language Result Execution time Memory
120639 2019-06-25T06:44:00 Z 송준혁(#2962) Minerals (JOI19_minerals) C++14
40 / 100
 215 ms 8968 KB 
#include <bits/stdc++.h>
#include "minerals.h"
using namespace std;

set<int> nw, nx;
int M1[50505], num=1;

void Change(){
    for (int x : nx) if (nw.lower_bound(x) == nw.end() || *nw.lower_bound(x) != x) Query(x);
    for (int x : nw) if (nx.lower_bound(x) == nx.end() || *nx.lower_bound(x) != x) Query(x);
    nw = nx;
}

void Find(int s, int e, vector<int> M2, bool tf){
    if (s == e){
        Answer(M1[s], M2[0]);
        return;
    }
    int mid = (s+e)/2;
    vector<int> L, R;
    nx.clear();
    for (int i=s; i<=mid; i++) nx.insert(M1[i]);
    if (tf) for (int x : M2) nx.insert(x);
    Change();
    int lq;
    if (tf) lq = e-s+1;
    else lq = mid-s+1;
    for (int x : M2){
        int ret = Query(x);
        if (tf) nw.erase(x);
        else nw.insert(x);
        if (lq == ret) L.push_back(x);
        else R.push_back(x);
        lq = ret;
    }
    Find(s, mid, L, !tf);
    Find(mid+1, e, R, !tf);
}

void Solve(int N) {
    for (int i=1; i<=2*N; i++) nx.insert(i);
    Change();
    vector<int> M2;
    for (int i=1; i<=2*N; i++){
        int ret = Query(i);
        if (N == ret) {
            M2.push_back(i);
            nw.erase(i);
        }
        else Query(i);
    }
    for (int x : nw) M1[num++] = x;
    Find(1, N, M2, false);
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 512 KB Output is correct
2 Correct 10 ms 776 KB Output is correct
3 Correct 21 ms 1280 KB Output is correct
4 Correct 45 ms 2056 KB Output is correct
5 Correct 90 ms 3456 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 10 ms 776 KB Output is correct
7 Correct 21 ms 1280 KB Output is correct
8 Correct 45 ms 2056 KB Output is correct
9 Correct 90 ms 3456 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 60 ms 2560 KB Output is correct
12 Correct 93 ms 3832 KB Output is correct
13 Correct 77 ms 3832 KB Output is correct
14 Correct 82 ms 3384 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 10 ms 776 KB Output is correct
7 Correct 21 ms 1280 KB Output is correct
8 Correct 45 ms 2056 KB Output is correct
9 Correct 90 ms 3456 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 60 ms 2560 KB Output is correct
12 Correct 93 ms 3832 KB Output is correct
13 Correct 77 ms 3832 KB Output is correct
14 Correct 82 ms 3384 KB Output is correct
15 Incorrect 215 ms 8968 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 10 ms 776 KB Output is correct
7 Correct 21 ms 1280 KB Output is correct
8 Correct 45 ms 2056 KB Output is correct
9 Correct 90 ms 3456 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 60 ms 2560 KB Output is correct
12 Correct 93 ms 3832 KB Output is correct
13 Correct 77 ms 3832 KB Output is correct
14 Correct 82 ms 3384 KB Output is correct
15 Incorrect 215 ms 8968 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 10 ms 776 KB Output is correct
7 Correct 21 ms 1280 KB Output is correct
8 Correct 45 ms 2056 KB Output is correct
9 Correct 90 ms 3456 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 60 ms 2560 KB Output is correct
12 Correct 93 ms 3832 KB Output is correct
13 Correct 77 ms 3832 KB Output is correct
14 Correct 82 ms 3384 KB Output is correct
15 Incorrect 215 ms 8968 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 10 ms 776 KB Output is correct
7 Correct 21 ms 1280 KB Output is correct
8 Correct 45 ms 2056 KB Output is correct
9 Correct 90 ms 3456 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 60 ms 2560 KB Output is correct
12 Correct 93 ms 3832 KB Output is correct
13 Correct 77 ms 3832 KB Output is correct
14 Correct 82 ms 3384 KB Output is correct
15 Incorrect 215 ms 8968 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 10 ms 776 KB Output is correct
7 Correct 21 ms 1280 KB Output is correct
8 Correct 45 ms 2056 KB Output is correct
9 Correct 90 ms 3456 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 60 ms 2560 KB Output is correct
12 Correct 93 ms 3832 KB Output is correct
13 Correct 77 ms 3832 KB Output is correct
14 Correct 82 ms 3384 KB Output is correct
15 Incorrect 215 ms 8968 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 6 ms 512 KB Output is correct
6 Correct 10 ms 776 KB Output is correct
7 Correct 21 ms 1280 KB Output is correct
8 Correct 45 ms 2056 KB Output is correct
9 Correct 90 ms 3456 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 60 ms 2560 KB Output is correct
12 Correct 93 ms 3832 KB Output is correct
13 Correct 77 ms 3832 KB Output is correct
14 Correct 82 ms 3384 KB Output is correct
15 Incorrect 215 ms 8968 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -