oj.uz

Submission #128867

# Submission time Handle Problem Language Result Execution time Memory
128867 2019-07-11T10:28:35 Z Osama_Alkhodairy Minerals (JOI19_minerals) C++17
80 / 100
 359 ms 6052 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 + r - 1) / 2;
    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() ; 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 244 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 10 ms 632 KB Output is correct
3 Correct 21 ms 816 KB Output is correct
4 Correct 43 ms 1272 KB Output is correct
5 Correct 102 ms 2080 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 244 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 10 ms 632 KB Output is correct
7 Correct 21 ms 816 KB Output is correct
8 Correct 43 ms 1272 KB Output is correct
9 Correct 102 ms 2080 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 67 ms 1744 KB Output is correct
12 Correct 113 ms 2340 KB Output is correct
13 Correct 87 ms 2344 KB Output is correct
14 Correct 74 ms 2084 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 244 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 10 ms 632 KB Output is correct
7 Correct 21 ms 816 KB Output is correct
8 Correct 43 ms 1272 KB Output is correct
9 Correct 102 ms 2080 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 67 ms 1744 KB Output is correct
12 Correct 113 ms 2340 KB Output is correct
13 Correct 87 ms 2344 KB Output is correct
14 Correct 74 ms 2084 KB Output is correct
15 Correct 337 ms 5796 KB Output is correct
16 Correct 340 ms 5588 KB Output is correct
17 Correct 242 ms 5608 KB Output is correct
18 Correct 216 ms 4960 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 244 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 10 ms 632 KB Output is correct
7 Correct 21 ms 816 KB Output is correct
8 Correct 43 ms 1272 KB Output is correct
9 Correct 102 ms 2080 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 67 ms 1744 KB Output is correct
12 Correct 113 ms 2340 KB Output is correct
13 Correct 87 ms 2344 KB Output is correct
14 Correct 74 ms 2084 KB Output is correct
15 Correct 337 ms 5796 KB Output is correct
16 Correct 340 ms 5588 KB Output is correct
17 Correct 242 ms 5608 KB Output is correct
18 Correct 216 ms 4960 KB Output is correct
19 Correct 347 ms 5832 KB Output is correct
20 Correct 351 ms 5892 KB Output is correct
21 Correct 251 ms 5752 KB Output is correct
22 Correct 223 ms 5024 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 244 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 10 ms 632 KB Output is correct
7 Correct 21 ms 816 KB Output is correct
8 Correct 43 ms 1272 KB Output is correct
9 Correct 102 ms 2080 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 67 ms 1744 KB Output is correct
12 Correct 113 ms 2340 KB Output is correct
13 Correct 87 ms 2344 KB Output is correct
14 Correct 74 ms 2084 KB Output is correct
15 Correct 337 ms 5796 KB Output is correct
16 Correct 340 ms 5588 KB Output is correct
17 Correct 242 ms 5608 KB Output is correct
18 Correct 216 ms 4960 KB Output is correct
19 Correct 347 ms 5832 KB Output is correct
20 Correct 351 ms 5892 KB Output is correct
21 Correct 251 ms 5752 KB Output is correct
22 Correct 223 ms 5024 KB Output is correct
23 Correct 359 ms 6032 KB Output is correct
24 Correct 358 ms 5876 KB Output is correct
25 Correct 252 ms 6000 KB Output is correct
26 Correct 234 ms 5116 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 244 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 10 ms 632 KB Output is correct
7 Correct 21 ms 816 KB Output is correct
8 Correct 43 ms 1272 KB Output is correct
9 Correct 102 ms 2080 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 67 ms 1744 KB Output is correct
12 Correct 113 ms 2340 KB Output is correct
13 Correct 87 ms 2344 KB Output is correct
14 Correct 74 ms 2084 KB Output is correct
15 Correct 337 ms 5796 KB Output is correct
16 Correct 340 ms 5588 KB Output is correct
17 Correct 242 ms 5608 KB Output is correct
18 Correct 216 ms 4960 KB Output is correct
19 Correct 347 ms 5832 KB Output is correct
20 Correct 351 ms 5892 KB Output is correct
21 Correct 251 ms 5752 KB Output is correct
22 Correct 223 ms 5024 KB Output is correct
23 Correct 359 ms 6032 KB Output is correct
24 Correct 358 ms 5876 KB Output is correct
25 Correct 252 ms 6000 KB Output is correct
26 Correct 234 ms 5116 KB Output is correct
27 Incorrect 357 ms 6052 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 244 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 10 ms 632 KB Output is correct
7 Correct 21 ms 816 KB Output is correct
8 Correct 43 ms 1272 KB Output is correct
9 Correct 102 ms 2080 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 67 ms 1744 KB Output is correct
12 Correct 113 ms 2340 KB Output is correct
13 Correct 87 ms 2344 KB Output is correct
14 Correct 74 ms 2084 KB Output is correct
15 Correct 337 ms 5796 KB Output is correct
16 Correct 340 ms 5588 KB Output is correct
17 Correct 242 ms 5608 KB Output is correct
18 Correct 216 ms 4960 KB Output is correct
19 Correct 347 ms 5832 KB Output is correct
20 Correct 351 ms 5892 KB Output is correct
21 Correct 251 ms 5752 KB Output is correct
22 Correct 223 ms 5024 KB Output is correct
23 Correct 359 ms 6032 KB Output is correct
24 Correct 358 ms 5876 KB Output is correct
25 Correct 252 ms 6000 KB Output is correct
26 Correct 234 ms 5116 KB Output is correct
27 Incorrect 357 ms 6052 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 244 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 10 ms 632 KB Output is correct
7 Correct 21 ms 816 KB Output is correct
8 Correct 43 ms 1272 KB Output is correct
9 Correct 102 ms 2080 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 67 ms 1744 KB Output is correct
12 Correct 113 ms 2340 KB Output is correct
13 Correct 87 ms 2344 KB Output is correct
14 Correct 74 ms 2084 KB Output is correct
15 Correct 337 ms 5796 KB Output is correct
16 Correct 340 ms 5588 KB Output is correct
17 Correct 242 ms 5608 KB Output is correct
18 Correct 216 ms 4960 KB Output is correct
19 Correct 347 ms 5832 KB Output is correct
20 Correct 351 ms 5892 KB Output is correct
21 Correct 251 ms 5752 KB Output is correct
22 Correct 223 ms 5024 KB Output is correct
23 Correct 359 ms 6032 KB Output is correct
24 Correct 358 ms 5876 KB Output is correct
25 Correct 252 ms 6000 KB Output is correct
26 Correct 234 ms 5116 KB Output is correct
27 Incorrect 357 ms 6052 KB Wrong Answer [2]
28 Halted 0 ms 0 KB -