oj.uz

Submission #489315

# Submission time Handle Problem Language Result Execution time Memory
489315 2021-11-22T09:15:00 Z balbit Minerals (JOI19_minerals) C++14
90 / 100
 68 ms 3008 KB 
#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif

const int iinf = 1e9+10;
const ll inf = 1ll<<60;
const ll mod = 1e9+7 ;


void GG(){cout<<"0\n"; exit(0);}

ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 1e5+5;
namespace {

vector<int> g1, g2; // group 1, group 2, each is a permutation
bool in[maxn]; // 0-based

int to[maxn]; // to[A] = B => g1[A] matches with g2[B]

int lst = 0;
int QU(int x) {
    in[x] ^= 1;
    return lst = Query(x+1);
}
};


void gogo(int l, int r, vector<int> a) {
    assert(r-l+1 == SZ(a));
    bug(l,r);
//    for (int x : a) cout<<x<<' ';
//    cout<<endl;
    if (l == r) {
        to[a[0]] = l;
        return;
    }
    int mid = (l+r)/2;
    // flip the range from mid+1 to r
    for (int i = mid+1; i<=r; ++i) {
        QU(g2[i]);
    }

    vector<int> tol, tor;
    random_shuffle(ALL(a));
    int i = 0;
    for (i = 0; i<SZ(a); ++i) {
        if (SZ(tor) == (r-mid) || SZ(tol) == (mid-l+1)) {
            if (SZ(tol) < (mid-l+1)) {
                tol.pb(a[i]);
            }
            else {
                tor.pb(a[i]);
            }
            continue;
        }
        int pv = lst;
        bool inset = QU(g1[a[i]]) != pv;
        bool setisleft = in[g2[l]];
        if (inset ^ setisleft ^ 1) {
            tor.pb(a[i]);
//            bug(a[i], "going right");
        }else{
            tol.pb(a[i]);
//            bug(a[i], "going left");
        }
    }
    gogo(l,mid,tol); gogo(mid+1,r,tor);
}

void Solve(int N) {
    int prv = 0;
    REP(i,N*2) {
        if (QU(i) != prv) {
            ++prv; g1.pb(i);
        }else{
            g2.pb(i);
        }
    }
    #ifdef BALBIT
    for (int x : g1) cout<<x<<' ';
    cout<<endl;
    for (int x : g2) cout<<x<<' ';
    cout<<endl;
    #endif // BALBIT

    // now, everything is inside the mineral machine

//    bool inside = 1;
//
//    RREP(bit, 16) {
//        // which bit do I care about?
//        int needmove = 0;
//        REP(i,N) {
//            if (((i>>bit)&1) ^ in[g2[i]]) {
//                ++needmove; // need to move if
//            }
//        }
//        bool flp = 0;
//        if (N-needmove < needmove) {
//            flp = 1;
//        }
//        REP(i,N) {
//            if (((i>>bit)&1) ^ flp ^ in[g2[i]]) {
//                QU(g2[i]);
//            }
//        }
//
//        REP(i,N) {
//            int tmp = lst;
//            if ((QU(g1[i]) != tmp) ^ flp ^ 1) {
//                // this is inside the set of g2
//                to[i] += (1<<bit);
//            } // remove it
//        }
//    }
    vector<int> st(N);
    REP(i,N) st[i] = i;
    gogo(0,N-1,st);

    REP(i,N) {
        bug(i, to[i]);
    }

    REP(i,N) {
        Answer(1+g1[i], 1+g2[to[i]]);
    }

}




/*
4
1 5
2 6
3 4
7 8
*/

Subtask #1
6.0 / 6.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 3 ms 328 KB Output is correct
3 Correct 5 ms 456 KB Output is correct
4 Correct 8 ms 712 KB Output is correct
5 Correct 17 ms 1224 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 284 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 3 ms 328 KB Output is correct
7 Correct 5 ms 456 KB Output is correct
8 Correct 8 ms 712 KB Output is correct
9 Correct 17 ms 1224 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 11 ms 968 KB Output is correct
12 Correct 19 ms 1184 KB Output is correct
13 Correct 20 ms 1268 KB Output is correct
14 Correct 16 ms 1208 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 284 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 3 ms 328 KB Output is correct
7 Correct 5 ms 456 KB Output is correct
8 Correct 8 ms 712 KB Output is correct
9 Correct 17 ms 1224 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 11 ms 968 KB Output is correct
12 Correct 19 ms 1184 KB Output is correct
13 Correct 20 ms 1268 KB Output is correct
14 Correct 16 ms 1208 KB Output is correct
15 Correct 54 ms 2748 KB Output is correct
16 Correct 54 ms 2756 KB Output is correct
17 Correct 47 ms 2604 KB Output is correct
18 Correct 41 ms 2496 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 284 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 3 ms 328 KB Output is correct
7 Correct 5 ms 456 KB Output is correct
8 Correct 8 ms 712 KB Output is correct
9 Correct 17 ms 1224 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 11 ms 968 KB Output is correct
12 Correct 19 ms 1184 KB Output is correct
13 Correct 20 ms 1268 KB Output is correct
14 Correct 16 ms 1208 KB Output is correct
15 Correct 54 ms 2748 KB Output is correct
16 Correct 54 ms 2756 KB Output is correct
17 Correct 47 ms 2604 KB Output is correct
18 Correct 41 ms 2496 KB Output is correct
19 Correct 54 ms 2744 KB Output is correct
20 Correct 50 ms 2676 KB Output is correct
21 Correct 46 ms 2748 KB Output is correct
22 Correct 42 ms 2556 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 284 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 3 ms 328 KB Output is correct
7 Correct 5 ms 456 KB Output is correct
8 Correct 8 ms 712 KB Output is correct
9 Correct 17 ms 1224 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 11 ms 968 KB Output is correct
12 Correct 19 ms 1184 KB Output is correct
13 Correct 20 ms 1268 KB Output is correct
14 Correct 16 ms 1208 KB Output is correct
15 Correct 54 ms 2748 KB Output is correct
16 Correct 54 ms 2756 KB Output is correct
17 Correct 47 ms 2604 KB Output is correct
18 Correct 41 ms 2496 KB Output is correct
19 Correct 54 ms 2744 KB Output is correct
20 Correct 50 ms 2676 KB Output is correct
21 Correct 46 ms 2748 KB Output is correct
22 Correct 42 ms 2556 KB Output is correct
23 Correct 57 ms 2844 KB Output is correct
24 Correct 56 ms 2732 KB Output is correct
25 Correct 46 ms 2732 KB Output is correct
26 Correct 44 ms 2552 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 284 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 3 ms 328 KB Output is correct
7 Correct 5 ms 456 KB Output is correct
8 Correct 8 ms 712 KB Output is correct
9 Correct 17 ms 1224 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 11 ms 968 KB Output is correct
12 Correct 19 ms 1184 KB Output is correct
13 Correct 20 ms 1268 KB Output is correct
14 Correct 16 ms 1208 KB Output is correct
15 Correct 54 ms 2748 KB Output is correct
16 Correct 54 ms 2756 KB Output is correct
17 Correct 47 ms 2604 KB Output is correct
18 Correct 41 ms 2496 KB Output is correct
19 Correct 54 ms 2744 KB Output is correct
20 Correct 50 ms 2676 KB Output is correct
21 Correct 46 ms 2748 KB Output is correct
22 Correct 42 ms 2556 KB Output is correct
23 Correct 57 ms 2844 KB Output is correct
24 Correct 56 ms 2732 KB Output is correct
25 Correct 46 ms 2732 KB Output is correct
26 Correct 44 ms 2552 KB Output is correct
27 Correct 54 ms 2876 KB Output is correct
28 Correct 51 ms 2660 KB Output is correct
29 Correct 52 ms 2872 KB Output is correct
30 Correct 45 ms 2640 KB Output is correct

Subtask #8
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 284 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 3 ms 328 KB Output is correct
7 Correct 5 ms 456 KB Output is correct
8 Correct 8 ms 712 KB Output is correct
9 Correct 17 ms 1224 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 11 ms 968 KB Output is correct
12 Correct 19 ms 1184 KB Output is correct
13 Correct 20 ms 1268 KB Output is correct
14 Correct 16 ms 1208 KB Output is correct
15 Correct 54 ms 2748 KB Output is correct
16 Correct 54 ms 2756 KB Output is correct
17 Correct 47 ms 2604 KB Output is correct
18 Correct 41 ms 2496 KB Output is correct
19 Correct 54 ms 2744 KB Output is correct
20 Correct 50 ms 2676 KB Output is correct
21 Correct 46 ms 2748 KB Output is correct
22 Correct 42 ms 2556 KB Output is correct
23 Correct 57 ms 2844 KB Output is correct
24 Correct 56 ms 2732 KB Output is correct
25 Correct 46 ms 2732 KB Output is correct
26 Correct 44 ms 2552 KB Output is correct
27 Correct 54 ms 2876 KB Output is correct
28 Correct 51 ms 2660 KB Output is correct
29 Correct 52 ms 2872 KB Output is correct
30 Correct 45 ms 2640 KB Output is correct
31 Correct 68 ms 2872 KB Output is correct
32 Correct 60 ms 3008 KB Output is correct
33 Correct 52 ms 2940 KB Output is correct
34 Correct 46 ms 2712 KB Output is correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Correct 1 ms 284 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 3 ms 328 KB Output is correct
7 Correct 5 ms 456 KB Output is correct
8 Correct 8 ms 712 KB Output is correct
9 Correct 17 ms 1224 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 11 ms 968 KB Output is correct
12 Correct 19 ms 1184 KB Output is correct
13 Correct 20 ms 1268 KB Output is correct
14 Correct 16 ms 1208 KB Output is correct
15 Correct 54 ms 2748 KB Output is correct
16 Correct 54 ms 2756 KB Output is correct
17 Correct 47 ms 2604 KB Output is correct
18 Correct 41 ms 2496 KB Output is correct
19 Correct 54 ms 2744 KB Output is correct
20 Correct 50 ms 2676 KB Output is correct
21 Correct 46 ms 2748 KB Output is correct
22 Correct 42 ms 2556 KB Output is correct
23 Correct 57 ms 2844 KB Output is correct
24 Correct 56 ms 2732 KB Output is correct
25 Correct 46 ms 2732 KB Output is correct
26 Correct 44 ms 2552 KB Output is correct
27 Correct 54 ms 2876 KB Output is correct
28 Correct 51 ms 2660 KB Output is correct
29 Correct 52 ms 2872 KB Output is correct
30 Correct 45 ms 2640 KB Output is correct
31 Correct 68 ms 2872 KB Output is correct
32 Correct 60 ms 3008 KB Output is correct
33 Correct 52 ms 2940 KB Output is correct
34 Correct 46 ms 2712 KB Output is correct
35 Incorrect 56 ms 2796 KB Wrong Answer [2]
36 Halted 0 ms 0 KB -