oj.uz

Submission #674938

# Submission time Handle Problem Language Result Execution time Memory
674938 2022-12-26T16:15:29 Z urosk Minerals (JOI19_minerals) C++14
90 / 100
 66 ms 4484 KB 
#include "minerals.h"
#define here cerr<<"===========================================\n"
#define dbg(x) cerr<<#x<<": "<<x<<endl;
#include "bits/stdc++.h"
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll int
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {cerr<<#a<<": ";for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define cer(a) {cerr<<#a<<": ";for(ll x_ : a) cerr<<x_<< " ";cerr<<endl;}

#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll last = 0,n;
bool ask(ll i){
    ll cur = Query(i);
    bool ans = cur!=last;
    last = cur;
    return ans;
}
void reshi(vector<ll> l,vector<ll> r,bool f){
    n = sz(l);
    ll m = ceil(n*0.3);
    if(n==1){
        Answer(l[0],r[0]);
        return;
    }
    if(f) m = n-m;
    if(f){
        for(ll i = n-1;i>=m;i--) ask(l[i]);
    }else{
        for(ll i = 0;i<m;i++) ask(l[i]);
    }
    shuffle(all(r),rng);
    vector<ll> L,R;
    for(ll i = 0;i<n;i++){
        if(sz(L)==m) R.pb(r[i]);
        else if(sz(R)==n-m) L.pb(r[i]);
        else if(ask(r[i])) R.pb(r[i]);
        else L.pb(r[i]);
    }
    vector<ll> lL,lR;
    for(ll i = 0;i<m;i++) lL.pb(l[i]);
    for(ll i = m;i<n;i++) lR.pb(l[i]);
    reshi(lL,L,1);
    reshi(lR,R,0);
}
void Solve(int N) {
    n = N;
    vector<ll> l,r;
    for(ll i = 1;i<=2*n;i++){
        if(ask(i)) l.pb(i);
        else r.pb(i);
    }
    reshi(l,r,1);
}

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 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 464 KB Output is correct
3 Correct 5 ms 592 KB Output is correct
4 Correct 11 ms 976 KB Output is correct
5 Correct 19 ms 1776 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 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 5 ms 592 KB Output is correct
8 Correct 11 ms 976 KB Output is correct
9 Correct 19 ms 1776 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 13 ms 1288 KB Output is correct
12 Correct 22 ms 1744 KB Output is correct
13 Correct 19 ms 1780 KB Output is correct
14 Correct 21 ms 1708 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 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 5 ms 592 KB Output is correct
8 Correct 11 ms 976 KB Output is correct
9 Correct 19 ms 1776 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 13 ms 1288 KB Output is correct
12 Correct 22 ms 1744 KB Output is correct
13 Correct 19 ms 1780 KB Output is correct
14 Correct 21 ms 1708 KB Output is correct
15 Correct 61 ms 4004 KB Output is correct
16 Correct 56 ms 4080 KB Output is correct
17 Correct 49 ms 4008 KB Output is correct
18 Correct 49 ms 3832 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 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 5 ms 592 KB Output is correct
8 Correct 11 ms 976 KB Output is correct
9 Correct 19 ms 1776 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 13 ms 1288 KB Output is correct
12 Correct 22 ms 1744 KB Output is correct
13 Correct 19 ms 1780 KB Output is correct
14 Correct 21 ms 1708 KB Output is correct
15 Correct 61 ms 4004 KB Output is correct
16 Correct 56 ms 4080 KB Output is correct
17 Correct 49 ms 4008 KB Output is correct
18 Correct 49 ms 3832 KB Output is correct
19 Correct 54 ms 4152 KB Output is correct
20 Correct 55 ms 4088 KB Output is correct
21 Correct 51 ms 4064 KB Output is correct
22 Correct 53 ms 4036 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 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 5 ms 592 KB Output is correct
8 Correct 11 ms 976 KB Output is correct
9 Correct 19 ms 1776 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 13 ms 1288 KB Output is correct
12 Correct 22 ms 1744 KB Output is correct
13 Correct 19 ms 1780 KB Output is correct
14 Correct 21 ms 1708 KB Output is correct
15 Correct 61 ms 4004 KB Output is correct
16 Correct 56 ms 4080 KB Output is correct
17 Correct 49 ms 4008 KB Output is correct
18 Correct 49 ms 3832 KB Output is correct
19 Correct 54 ms 4152 KB Output is correct
20 Correct 55 ms 4088 KB Output is correct
21 Correct 51 ms 4064 KB Output is correct
22 Correct 53 ms 4036 KB Output is correct
23 Correct 56 ms 4244 KB Output is correct
24 Correct 61 ms 4184 KB Output is correct
25 Correct 57 ms 4176 KB Output is correct
26 Correct 58 ms 4140 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 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 5 ms 592 KB Output is correct
8 Correct 11 ms 976 KB Output is correct
9 Correct 19 ms 1776 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 13 ms 1288 KB Output is correct
12 Correct 22 ms 1744 KB Output is correct
13 Correct 19 ms 1780 KB Output is correct
14 Correct 21 ms 1708 KB Output is correct
15 Correct 61 ms 4004 KB Output is correct
16 Correct 56 ms 4080 KB Output is correct
17 Correct 49 ms 4008 KB Output is correct
18 Correct 49 ms 3832 KB Output is correct
19 Correct 54 ms 4152 KB Output is correct
20 Correct 55 ms 4088 KB Output is correct
21 Correct 51 ms 4064 KB Output is correct
22 Correct 53 ms 4036 KB Output is correct
23 Correct 56 ms 4244 KB Output is correct
24 Correct 61 ms 4184 KB Output is correct
25 Correct 57 ms 4176 KB Output is correct
26 Correct 58 ms 4140 KB Output is correct
27 Correct 58 ms 4288 KB Output is correct
28 Correct 58 ms 4380 KB Output is correct
29 Correct 54 ms 4368 KB Output is correct
30 Correct 53 ms 4164 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 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 5 ms 592 KB Output is correct
8 Correct 11 ms 976 KB Output is correct
9 Correct 19 ms 1776 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 13 ms 1288 KB Output is correct
12 Correct 22 ms 1744 KB Output is correct
13 Correct 19 ms 1780 KB Output is correct
14 Correct 21 ms 1708 KB Output is correct
15 Correct 61 ms 4004 KB Output is correct
16 Correct 56 ms 4080 KB Output is correct
17 Correct 49 ms 4008 KB Output is correct
18 Correct 49 ms 3832 KB Output is correct
19 Correct 54 ms 4152 KB Output is correct
20 Correct 55 ms 4088 KB Output is correct
21 Correct 51 ms 4064 KB Output is correct
22 Correct 53 ms 4036 KB Output is correct
23 Correct 56 ms 4244 KB Output is correct
24 Correct 61 ms 4184 KB Output is correct
25 Correct 57 ms 4176 KB Output is correct
26 Correct 58 ms 4140 KB Output is correct
27 Correct 58 ms 4288 KB Output is correct
28 Correct 58 ms 4380 KB Output is correct
29 Correct 54 ms 4368 KB Output is correct
30 Correct 53 ms 4164 KB Output is correct
31 Correct 61 ms 4468 KB Output is correct
32 Correct 58 ms 4480 KB Output is correct
33 Correct 63 ms 4420 KB Output is correct
34 Correct 56 ms 4256 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 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 5 ms 592 KB Output is correct
8 Correct 11 ms 976 KB Output is correct
9 Correct 19 ms 1776 KB Output is correct
10 Correct 2 ms 336 KB Output is correct
11 Correct 13 ms 1288 KB Output is correct
12 Correct 22 ms 1744 KB Output is correct
13 Correct 19 ms 1780 KB Output is correct
14 Correct 21 ms 1708 KB Output is correct
15 Correct 61 ms 4004 KB Output is correct
16 Correct 56 ms 4080 KB Output is correct
17 Correct 49 ms 4008 KB Output is correct
18 Correct 49 ms 3832 KB Output is correct
19 Correct 54 ms 4152 KB Output is correct
20 Correct 55 ms 4088 KB Output is correct
21 Correct 51 ms 4064 KB Output is correct
22 Correct 53 ms 4036 KB Output is correct
23 Correct 56 ms 4244 KB Output is correct
24 Correct 61 ms 4184 KB Output is correct
25 Correct 57 ms 4176 KB Output is correct
26 Correct 58 ms 4140 KB Output is correct
27 Correct 58 ms 4288 KB Output is correct
28 Correct 58 ms 4380 KB Output is correct
29 Correct 54 ms 4368 KB Output is correct
30 Correct 53 ms 4164 KB Output is correct
31 Correct 61 ms 4468 KB Output is correct
32 Correct 58 ms 4480 KB Output is correct
33 Correct 63 ms 4420 KB Output is correct
34 Correct 56 ms 4256 KB Output is correct
35 Correct 60 ms 4484 KB Output is correct
36 Correct 66 ms 4468 KB Output is correct
37 Incorrect 58 ms 4452 KB Wrong Answer [2]
38 Halted 0 ms 0 KB -