oj.uz

Submission #128293

# Submission time Handle Problem Language Result Execution time Memory
128293 2019-07-10T16:04:35 Z Osama_Alkhodairy Minerals (JOI19_minerals) C++17
40 / 100
 223 ms 5060 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 252 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 8 ms 504 KB Output is correct
3 Correct 17 ms 760 KB Output is correct
4 Correct 33 ms 1400 KB Output is correct
5 Correct 67 ms 2168 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 252 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 8 ms 504 KB Output is correct
7 Correct 17 ms 760 KB Output is correct
8 Correct 33 ms 1400 KB Output is correct
9 Correct 67 ms 2168 KB Output is correct
10 Correct 7 ms 504 KB Output is correct
11 Correct 72 ms 1656 KB Output is correct
12 Correct 116 ms 2168 KB Output is correct
13 Correct 99 ms 2296 KB Output is correct
14 Correct 86 ms 2168 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 252 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 8 ms 504 KB Output is correct
7 Correct 17 ms 760 KB Output is correct
8 Correct 33 ms 1400 KB Output is correct
9 Correct 67 ms 2168 KB Output is correct
10 Correct 7 ms 504 KB Output is correct
11 Correct 72 ms 1656 KB Output is correct
12 Correct 116 ms 2168 KB Output is correct
13 Correct 99 ms 2296 KB Output is correct
14 Correct 86 ms 2168 KB Output is correct
15 Incorrect 223 ms 5060 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 252 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 8 ms 504 KB Output is correct
7 Correct 17 ms 760 KB Output is correct
8 Correct 33 ms 1400 KB Output is correct
9 Correct 67 ms 2168 KB Output is correct
10 Correct 7 ms 504 KB Output is correct
11 Correct 72 ms 1656 KB Output is correct
12 Correct 116 ms 2168 KB Output is correct
13 Correct 99 ms 2296 KB Output is correct
14 Correct 86 ms 2168 KB Output is correct
15 Incorrect 223 ms 5060 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 252 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 8 ms 504 KB Output is correct
7 Correct 17 ms 760 KB Output is correct
8 Correct 33 ms 1400 KB Output is correct
9 Correct 67 ms 2168 KB Output is correct
10 Correct 7 ms 504 KB Output is correct
11 Correct 72 ms 1656 KB Output is correct
12 Correct 116 ms 2168 KB Output is correct
13 Correct 99 ms 2296 KB Output is correct
14 Correct 86 ms 2168 KB Output is correct
15 Incorrect 223 ms 5060 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 252 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 8 ms 504 KB Output is correct
7 Correct 17 ms 760 KB Output is correct
8 Correct 33 ms 1400 KB Output is correct
9 Correct 67 ms 2168 KB Output is correct
10 Correct 7 ms 504 KB Output is correct
11 Correct 72 ms 1656 KB Output is correct
12 Correct 116 ms 2168 KB Output is correct
13 Correct 99 ms 2296 KB Output is correct
14 Correct 86 ms 2168 KB Output is correct
15 Incorrect 223 ms 5060 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 252 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 8 ms 504 KB Output is correct
7 Correct 17 ms 760 KB Output is correct
8 Correct 33 ms 1400 KB Output is correct
9 Correct 67 ms 2168 KB Output is correct
10 Correct 7 ms 504 KB Output is correct
11 Correct 72 ms 1656 KB Output is correct
12 Correct 116 ms 2168 KB Output is correct
13 Correct 99 ms 2296 KB Output is correct
14 Correct 86 ms 2168 KB Output is correct
15 Incorrect 223 ms 5060 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 252 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 8 ms 504 KB Output is correct
7 Correct 17 ms 760 KB Output is correct
8 Correct 33 ms 1400 KB Output is correct
9 Correct 67 ms 2168 KB Output is correct
10 Correct 7 ms 504 KB Output is correct
11 Correct 72 ms 1656 KB Output is correct
12 Correct 116 ms 2168 KB Output is correct
13 Correct 99 ms 2296 KB Output is correct
14 Correct 86 ms 2168 KB Output is correct
15 Incorrect 223 ms 5060 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -