oj.uz

Submission #128809

# Submission time Handle Problem Language Result Execution time Memory
128809 2019-07-11T09:47:40 Z Osama_Alkhodairy Minerals (JOI19_minerals) C++17
40 / 100
 339 ms 5392 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) / 2;
    for(int i = l ; i <= mid ; i++){
        if(active.count(e[i])) continue;
        query(e[i]);
    }
    while(1){
        auto it = active.upper_bound(e[mid]);
        if(it == active.end() || *it > e[r]) break;
        query(*it);
    }
    vector <int> left, right;
    for(auto &i : cur){
        int las = curq;
        int x = query(i);
        if(x == las) left.push_back(i);
        else right.push_back(i);
        //~ query(i);
    }
    solve(l, mid, left);
    solve(mid + 1, r, right);
}
void Solve(int N){
    int prev = 0;
    for(int i = 1 ; i <= 2 * N ; i++){
        int cur = query(i);
        if(cur != prev) s.push_back(i);
        else e.push_back(i);
        prev = cur;
    }
    for(auto &i : s) query(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 376 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 376 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 376 KB Output is correct
2 Correct 11 ms 664 KB Output is correct
3 Correct 20 ms 888 KB Output is correct
4 Correct 50 ms 1400 KB Output is correct
5 Correct 98 ms 2312 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 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 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 11 ms 664 KB Output is correct
7 Correct 20 ms 888 KB Output is correct
8 Correct 50 ms 1400 KB Output is correct
9 Correct 98 ms 2312 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 66 ms 1596 KB Output is correct
12 Correct 109 ms 2372 KB Output is correct
13 Correct 95 ms 2168 KB Output is correct
14 Correct 76 ms 2180 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 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 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 11 ms 664 KB Output is correct
7 Correct 20 ms 888 KB Output is correct
8 Correct 50 ms 1400 KB Output is correct
9 Correct 98 ms 2312 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 66 ms 1596 KB Output is correct
12 Correct 109 ms 2372 KB Output is correct
13 Correct 95 ms 2168 KB Output is correct
14 Correct 76 ms 2180 KB Output is correct
15 Incorrect 339 ms 5392 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 376 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 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 11 ms 664 KB Output is correct
7 Correct 20 ms 888 KB Output is correct
8 Correct 50 ms 1400 KB Output is correct
9 Correct 98 ms 2312 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 66 ms 1596 KB Output is correct
12 Correct 109 ms 2372 KB Output is correct
13 Correct 95 ms 2168 KB Output is correct
14 Correct 76 ms 2180 KB Output is correct
15 Incorrect 339 ms 5392 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 376 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 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 11 ms 664 KB Output is correct
7 Correct 20 ms 888 KB Output is correct
8 Correct 50 ms 1400 KB Output is correct
9 Correct 98 ms 2312 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 66 ms 1596 KB Output is correct
12 Correct 109 ms 2372 KB Output is correct
13 Correct 95 ms 2168 KB Output is correct
14 Correct 76 ms 2180 KB Output is correct
15 Incorrect 339 ms 5392 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 376 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 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 11 ms 664 KB Output is correct
7 Correct 20 ms 888 KB Output is correct
8 Correct 50 ms 1400 KB Output is correct
9 Correct 98 ms 2312 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 66 ms 1596 KB Output is correct
12 Correct 109 ms 2372 KB Output is correct
13 Correct 95 ms 2168 KB Output is correct
14 Correct 76 ms 2180 KB Output is correct
15 Incorrect 339 ms 5392 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 376 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 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 11 ms 664 KB Output is correct
7 Correct 20 ms 888 KB Output is correct
8 Correct 50 ms 1400 KB Output is correct
9 Correct 98 ms 2312 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 66 ms 1596 KB Output is correct
12 Correct 109 ms 2372 KB Output is correct
13 Correct 95 ms 2168 KB Output is correct
14 Correct 76 ms 2180 KB Output is correct
15 Incorrect 339 ms 5392 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 376 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 376 KB Output is correct
5 Correct 6 ms 376 KB Output is correct
6 Correct 11 ms 664 KB Output is correct
7 Correct 20 ms 888 KB Output is correct
8 Correct 50 ms 1400 KB Output is correct
9 Correct 98 ms 2312 KB Output is correct
10 Correct 6 ms 376 KB Output is correct
11 Correct 66 ms 1596 KB Output is correct
12 Correct 109 ms 2372 KB Output is correct
13 Correct 95 ms 2168 KB Output is correct
14 Correct 76 ms 2180 KB Output is correct
15 Incorrect 339 ms 5392 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -