oj.uz

Submission #824958

# Submission time Handle Problem Language Result Execution time Memory
824958 2023-08-14T12:32:01 Z sunwukong123 Minerals (JOI19_minerals) C++14
90 / 100
 148 ms 7240 KB 
#include "minerals.h"
#include <bits/stdc++.h>
using namespace std; 
void debug_out() {cerr<<endl;}
template <typename Head, typename... Tail>
void debug_out(Head _H, Tail... _T) {cerr<<" "<<to_string(_H);debug_out(_T...);}
#define debug(...) cerr<<"["<<#__VA_ARGS__<<"]:",debug_out(__VA_ARGS__)
const int MAXN = -1;
const int inf=1000000500ll;
const int MOD = (int)1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef pair<int,int> pi;
int n;
vector<int> v1,v2;
set<int> s1,s2;
set<int> s;
vector<pair<int,int>> out;
int lst;

bool has(int x){
    int q=Query(x);
    bool can=(lst==q);
    lst=q;
    return can;
}
void dnc(vector<int> L, vector<int> R, bool boo){
    assert(L.size()==R.size());
    if(L.size() == 1 && R.size() == 1){
        out.push_back({L[0],R[0]});
        return;
    }
    int mi;
    if(boo){
        mi=round((0.62) * (double)R.size());
    } else{
        mi=round((0.38) * (double)R.size());
    }

    vector<int> Llf, Lrg, Rlf, Rrg;
    unordered_set<int> w1;
    for(int i=0;i<mi;i++){ // [0,mi) is the set i want to query
        w1.insert(R[i]);
        if(s.find(R[i]) == s.end()){
            lst=Query(R[i]);
            s.insert(R[i]);
        }
    }
    
    vector<int> del;
    for(auto x:s){
        if(w1.find(x) == w1.end()){
            del.push_back(x);
        }
    }
    for(auto x:del){
        lst=Query(x);
        s.erase(x);
    }
    for(int i=0;i<(int)L.size()-1;i++){
        int x=L[i];
        bool hh=has(x);
        if(hh){
            Llf.push_back(x);
        } else{
            Lrg.push_back(x);
        }
    }
    
    for(int i=0;i<mi;i++){
        Rlf.push_back(R[i]);
    }
    for(int i=mi;i<(int)R.size();i++){
        Rrg.push_back(R[i]);
    }
    if(Llf.size() != Rlf.size()){
        Llf.push_back(L.back());
    } else{
        Lrg.push_back(L.back());
    }
    dnc(Llf,Rlf,1);
    dnc(Lrg,Rrg,0);
}
void Solve(int N) {
    n=N;
    vector<int> idx;
    for(int i=1;i<=2*n;i++){
        idx.push_back(i);
    }
    shuffle(idx.begin(),idx.end(),rng);
    for(int i=1;i<=2*n;i++){
        int x=idx[i-1];
        int q=Query(x);

        if(q==lst){
            v2.push_back(x);
        } else{
            v1.push_back(x);
        }
        lst=q;
    }
    
    
    for(auto x:v2){
        s.insert(x);
    }
    dnc(v1,v2,1);
    for(auto x:out){
        Answer(x.first,x.second);
    }
}

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 464 KB Output is correct
2 Correct 4 ms 592 KB Output is correct
3 Correct 9 ms 992 KB Output is correct
4 Correct 22 ms 1612 KB Output is correct
5 Correct 39 ms 2736 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 4 ms 592 KB Output is correct
7 Correct 9 ms 992 KB Output is correct
8 Correct 22 ms 1612 KB Output is correct
9 Correct 39 ms 2736 KB Output is correct
10 Correct 2 ms 464 KB Output is correct
11 Correct 24 ms 2024 KB Output is correct
12 Correct 37 ms 2796 KB Output is correct
13 Correct 38 ms 2788 KB Output is correct
14 Correct 38 ms 2744 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 4 ms 592 KB Output is correct
7 Correct 9 ms 992 KB Output is correct
8 Correct 22 ms 1612 KB Output is correct
9 Correct 39 ms 2736 KB Output is correct
10 Correct 2 ms 464 KB Output is correct
11 Correct 24 ms 2024 KB Output is correct
12 Correct 37 ms 2796 KB Output is correct
13 Correct 38 ms 2788 KB Output is correct
14 Correct 38 ms 2744 KB Output is correct
15 Correct 110 ms 6600 KB Output is correct
16 Correct 114 ms 6844 KB Output is correct
17 Correct 112 ms 6640 KB Output is correct
18 Correct 110 ms 6448 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 4 ms 592 KB Output is correct
7 Correct 9 ms 992 KB Output is correct
8 Correct 22 ms 1612 KB Output is correct
9 Correct 39 ms 2736 KB Output is correct
10 Correct 2 ms 464 KB Output is correct
11 Correct 24 ms 2024 KB Output is correct
12 Correct 37 ms 2796 KB Output is correct
13 Correct 38 ms 2788 KB Output is correct
14 Correct 38 ms 2744 KB Output is correct
15 Correct 110 ms 6600 KB Output is correct
16 Correct 114 ms 6844 KB Output is correct
17 Correct 112 ms 6640 KB Output is correct
18 Correct 110 ms 6448 KB Output is correct
19 Correct 114 ms 6708 KB Output is correct
20 Correct 121 ms 6832 KB Output is correct
21 Correct 113 ms 6712 KB Output is correct
22 Correct 114 ms 6512 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 4 ms 592 KB Output is correct
7 Correct 9 ms 992 KB Output is correct
8 Correct 22 ms 1612 KB Output is correct
9 Correct 39 ms 2736 KB Output is correct
10 Correct 2 ms 464 KB Output is correct
11 Correct 24 ms 2024 KB Output is correct
12 Correct 37 ms 2796 KB Output is correct
13 Correct 38 ms 2788 KB Output is correct
14 Correct 38 ms 2744 KB Output is correct
15 Correct 110 ms 6600 KB Output is correct
16 Correct 114 ms 6844 KB Output is correct
17 Correct 112 ms 6640 KB Output is correct
18 Correct 110 ms 6448 KB Output is correct
19 Correct 114 ms 6708 KB Output is correct
20 Correct 121 ms 6832 KB Output is correct
21 Correct 113 ms 6712 KB Output is correct
22 Correct 114 ms 6512 KB Output is correct
23 Correct 127 ms 6788 KB Output is correct
24 Correct 117 ms 6832 KB Output is correct
25 Correct 117 ms 6832 KB Output is correct
26 Correct 119 ms 6644 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 4 ms 592 KB Output is correct
7 Correct 9 ms 992 KB Output is correct
8 Correct 22 ms 1612 KB Output is correct
9 Correct 39 ms 2736 KB Output is correct
10 Correct 2 ms 464 KB Output is correct
11 Correct 24 ms 2024 KB Output is correct
12 Correct 37 ms 2796 KB Output is correct
13 Correct 38 ms 2788 KB Output is correct
14 Correct 38 ms 2744 KB Output is correct
15 Correct 110 ms 6600 KB Output is correct
16 Correct 114 ms 6844 KB Output is correct
17 Correct 112 ms 6640 KB Output is correct
18 Correct 110 ms 6448 KB Output is correct
19 Correct 114 ms 6708 KB Output is correct
20 Correct 121 ms 6832 KB Output is correct
21 Correct 113 ms 6712 KB Output is correct
22 Correct 114 ms 6512 KB Output is correct
23 Correct 127 ms 6788 KB Output is correct
24 Correct 117 ms 6832 KB Output is correct
25 Correct 117 ms 6832 KB Output is correct
26 Correct 119 ms 6644 KB Output is correct
27 Correct 122 ms 6944 KB Output is correct
28 Correct 130 ms 7008 KB Output is correct
29 Correct 125 ms 7036 KB Output is correct
30 Correct 121 ms 6736 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 4 ms 592 KB Output is correct
7 Correct 9 ms 992 KB Output is correct
8 Correct 22 ms 1612 KB Output is correct
9 Correct 39 ms 2736 KB Output is correct
10 Correct 2 ms 464 KB Output is correct
11 Correct 24 ms 2024 KB Output is correct
12 Correct 37 ms 2796 KB Output is correct
13 Correct 38 ms 2788 KB Output is correct
14 Correct 38 ms 2744 KB Output is correct
15 Correct 110 ms 6600 KB Output is correct
16 Correct 114 ms 6844 KB Output is correct
17 Correct 112 ms 6640 KB Output is correct
18 Correct 110 ms 6448 KB Output is correct
19 Correct 114 ms 6708 KB Output is correct
20 Correct 121 ms 6832 KB Output is correct
21 Correct 113 ms 6712 KB Output is correct
22 Correct 114 ms 6512 KB Output is correct
23 Correct 127 ms 6788 KB Output is correct
24 Correct 117 ms 6832 KB Output is correct
25 Correct 117 ms 6832 KB Output is correct
26 Correct 119 ms 6644 KB Output is correct
27 Correct 122 ms 6944 KB Output is correct
28 Correct 130 ms 7008 KB Output is correct
29 Correct 125 ms 7036 KB Output is correct
30 Correct 121 ms 6736 KB Output is correct
31 Correct 126 ms 7044 KB Output is correct
32 Correct 148 ms 7000 KB Output is correct
33 Correct 128 ms 7020 KB Output is correct
34 Correct 126 ms 6928 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 2 ms 464 KB Output is correct
6 Correct 4 ms 592 KB Output is correct
7 Correct 9 ms 992 KB Output is correct
8 Correct 22 ms 1612 KB Output is correct
9 Correct 39 ms 2736 KB Output is correct
10 Correct 2 ms 464 KB Output is correct
11 Correct 24 ms 2024 KB Output is correct
12 Correct 37 ms 2796 KB Output is correct
13 Correct 38 ms 2788 KB Output is correct
14 Correct 38 ms 2744 KB Output is correct
15 Correct 110 ms 6600 KB Output is correct
16 Correct 114 ms 6844 KB Output is correct
17 Correct 112 ms 6640 KB Output is correct
18 Correct 110 ms 6448 KB Output is correct
19 Correct 114 ms 6708 KB Output is correct
20 Correct 121 ms 6832 KB Output is correct
21 Correct 113 ms 6712 KB Output is correct
22 Correct 114 ms 6512 KB Output is correct
23 Correct 127 ms 6788 KB Output is correct
24 Correct 117 ms 6832 KB Output is correct
25 Correct 117 ms 6832 KB Output is correct
26 Correct 119 ms 6644 KB Output is correct
27 Correct 122 ms 6944 KB Output is correct
28 Correct 130 ms 7008 KB Output is correct
29 Correct 125 ms 7036 KB Output is correct
30 Correct 121 ms 6736 KB Output is correct
31 Correct 126 ms 7044 KB Output is correct
32 Correct 148 ms 7000 KB Output is correct
33 Correct 128 ms 7020 KB Output is correct
34 Correct 126 ms 6928 KB Output is correct
35 Incorrect 126 ms 7240 KB Wrong Answer [2]
36 Halted 0 ms 0 KB -