oj.uz

Submission #128879

# Submission time Handle Problem Language Result Execution time Memory
128879 2019-07-11T10:35:08 Z Osama_Alkhodairy Minerals (JOI19_minerals) C++17
80 / 100
 412 ms 6132 KB 
#include <bits/stdc++.h>
#include "minerals.h"
//~ #include "grader.cpp"
using namespace std;
 
set <int> active; 
vector <int> s, e;
int curl, curr;
int curq;

int query(int x){
    if(active.count(x)) active.erase(x);
    else active.insert(x);
    return curq = Query(x);
}
void solve(int l, int r, vector <int> &cur){
    if(r < l) return;
    if(l == r){
        assert(cur.size() == 1);
        Answer(e[l], cur[0]);
        return;
    }
    int mid = l + floor((r - l) * 0.36);
    for(int i = l ; i <= mid ; i++){
        if(active.count(e[i])) continue;
        query(e[i]);
    }
    for(int i = mid + 1 ; i <= r ; i++){
        if(!active.count(e[i])) continue;
        query(e[i]);
    }
    vector <int> left, right;
    for(int i = 0 ; i < (int)cur.size() - 1 ; i++){
        int las = curq;
        query(cur[i]);
        if(curq == las) left.push_back(cur[i]);
        else right.push_back(cur[i]);
    }
    if((int)left.size() != mid - l + 1) left.push_back(cur.back());
    else right.push_back(cur.back());
    solve(l, mid, left);
    solve(mid + 1, r, right);
}
void Solve(int N){
    for(int i = 1 ; i <= 2 * N ; i++){
        int prev = curq;
        query(i);
        if(curq != prev) s.push_back(i);
        else e.push_back(i);
    }
    curl = 0;
    curr = N - 1;
    solve(0, N - 1, s);
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 252 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 504 KB Output is correct
2 Correct 10 ms 632 KB Output is correct
3 Correct 20 ms 888 KB Output is correct
4 Correct 45 ms 1360 KB Output is correct
5 Correct 96 ms 2288 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 10 ms 632 KB Output is correct
7 Correct 20 ms 888 KB Output is correct
8 Correct 45 ms 1360 KB Output is correct
9 Correct 96 ms 2288 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 64 ms 1656 KB Output is correct
12 Correct 106 ms 2488 KB Output is correct
13 Correct 82 ms 2424 KB Output is correct
14 Correct 72 ms 2168 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 10 ms 632 KB Output is correct
7 Correct 20 ms 888 KB Output is correct
8 Correct 45 ms 1360 KB Output is correct
9 Correct 96 ms 2288 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 64 ms 1656 KB Output is correct
12 Correct 106 ms 2488 KB Output is correct
13 Correct 82 ms 2424 KB Output is correct
14 Correct 72 ms 2168 KB Output is correct
15 Correct 330 ms 5804 KB Output is correct
16 Correct 324 ms 5748 KB Output is correct
17 Correct 242 ms 5528 KB Output is correct
18 Correct 211 ms 4852 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 10 ms 632 KB Output is correct
7 Correct 20 ms 888 KB Output is correct
8 Correct 45 ms 1360 KB Output is correct
9 Correct 96 ms 2288 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 64 ms 1656 KB Output is correct
12 Correct 106 ms 2488 KB Output is correct
13 Correct 82 ms 2424 KB Output is correct
14 Correct 72 ms 2168 KB Output is correct
15 Correct 330 ms 5804 KB Output is correct
16 Correct 324 ms 5748 KB Output is correct
17 Correct 242 ms 5528 KB Output is correct
18 Correct 211 ms 4852 KB Output is correct
19 Correct 335 ms 5796 KB Output is correct
20 Correct 336 ms 5792 KB Output is correct
21 Correct 249 ms 5732 KB Output is correct
22 Correct 220 ms 4980 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 10 ms 632 KB Output is correct
7 Correct 20 ms 888 KB Output is correct
8 Correct 45 ms 1360 KB Output is correct
9 Correct 96 ms 2288 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 64 ms 1656 KB Output is correct
12 Correct 106 ms 2488 KB Output is correct
13 Correct 82 ms 2424 KB Output is correct
14 Correct 72 ms 2168 KB Output is correct
15 Correct 330 ms 5804 KB Output is correct
16 Correct 324 ms 5748 KB Output is correct
17 Correct 242 ms 5528 KB Output is correct
18 Correct 211 ms 4852 KB Output is correct
19 Correct 335 ms 5796 KB Output is correct
20 Correct 336 ms 5792 KB Output is correct
21 Correct 249 ms 5732 KB Output is correct
22 Correct 220 ms 4980 KB Output is correct
23 Correct 354 ms 6072 KB Output is correct
24 Correct 412 ms 6048 KB Output is correct
25 Correct 257 ms 5872 KB Output is correct
26 Correct 224 ms 5240 KB Output is correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 10 ms 632 KB Output is correct
7 Correct 20 ms 888 KB Output is correct
8 Correct 45 ms 1360 KB Output is correct
9 Correct 96 ms 2288 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 64 ms 1656 KB Output is correct
12 Correct 106 ms 2488 KB Output is correct
13 Correct 82 ms 2424 KB Output is correct
14 Correct 72 ms 2168 KB Output is correct
15 Correct 330 ms 5804 KB Output is correct
16 Correct 324 ms 5748 KB Output is correct
17 Correct 242 ms 5528 KB Output is correct
18 Correct 211 ms 4852 KB Output is correct
19 Correct 335 ms 5796 KB Output is correct
20 Correct 336 ms 5792 KB Output is correct
21 Correct 249 ms 5732 KB Output is correct
22 Correct 220 ms 4980 KB Output is correct
23 Correct 354 ms 6072 KB Output is correct
24 Correct 412 ms 6048 KB Output is correct
25 Correct 257 ms 5872 KB Output is correct
26 Correct 224 ms 5240 KB Output is correct
27 Incorrect 347 ms 6132 KB Wrong Answer [2]
28 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 10 ms 632 KB Output is correct
7 Correct 20 ms 888 KB Output is correct
8 Correct 45 ms 1360 KB Output is correct
9 Correct 96 ms 2288 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 64 ms 1656 KB Output is correct
12 Correct 106 ms 2488 KB Output is correct
13 Correct 82 ms 2424 KB Output is correct
14 Correct 72 ms 2168 KB Output is correct
15 Correct 330 ms 5804 KB Output is correct
16 Correct 324 ms 5748 KB Output is correct
17 Correct 242 ms 5528 KB Output is correct
18 Correct 211 ms 4852 KB Output is correct
19 Correct 335 ms 5796 KB Output is correct
20 Correct 336 ms 5792 KB Output is correct
21 Correct 249 ms 5732 KB Output is correct
22 Correct 220 ms 4980 KB Output is correct
23 Correct 354 ms 6072 KB Output is correct
24 Correct 412 ms 6048 KB Output is correct
25 Correct 257 ms 5872 KB Output is correct
26 Correct 224 ms 5240 KB Output is correct
27 Incorrect 347 ms 6132 KB Wrong Answer [2]
28 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 6 ms 504 KB Output is correct
6 Correct 10 ms 632 KB Output is correct
7 Correct 20 ms 888 KB Output is correct
8 Correct 45 ms 1360 KB Output is correct
9 Correct 96 ms 2288 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 64 ms 1656 KB Output is correct
12 Correct 106 ms 2488 KB Output is correct
13 Correct 82 ms 2424 KB Output is correct
14 Correct 72 ms 2168 KB Output is correct
15 Correct 330 ms 5804 KB Output is correct
16 Correct 324 ms 5748 KB Output is correct
17 Correct 242 ms 5528 KB Output is correct
18 Correct 211 ms 4852 KB Output is correct
19 Correct 335 ms 5796 KB Output is correct
20 Correct 336 ms 5792 KB Output is correct
21 Correct 249 ms 5732 KB Output is correct
22 Correct 220 ms 4980 KB Output is correct
23 Correct 354 ms 6072 KB Output is correct
24 Correct 412 ms 6048 KB Output is correct
25 Correct 257 ms 5872 KB Output is correct
26 Correct 224 ms 5240 KB Output is correct
27 Incorrect 347 ms 6132 KB Wrong Answer [2]
28 Halted 0 ms 0 KB -