oj.uz

Submission #489311

# Submission time Handle Problem Language Result Execution time Memory
489311 2021-11-22T08:51:13 Z balbit Minerals (JOI19_minerals) C++14
75 / 100
 29 ms 2232 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 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
        }
    }

//    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
*/

Compilation message

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:88:10: warning: unused variable 'inside' [-Wunused-variable]
   88 |     bool inside = 1;
      |          ^~~~~~

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 0 ms 200 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 1 ms 360 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Correct 5 ms 584 KB Output is correct
5 Correct 8 ms 968 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 0 ms 200 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 360 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 5 ms 584 KB Output is correct
9 Correct 8 ms 968 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 5 ms 840 KB Output is correct
12 Correct 8 ms 968 KB Output is correct
13 Correct 7 ms 968 KB Output is correct
14 Correct 9 ms 968 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 0 ms 200 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 360 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 5 ms 584 KB Output is correct
9 Correct 8 ms 968 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 5 ms 840 KB Output is correct
12 Correct 8 ms 968 KB Output is correct
13 Correct 7 ms 968 KB Output is correct
14 Correct 9 ms 968 KB Output is correct
15 Correct 24 ms 2104 KB Output is correct
16 Correct 28 ms 2120 KB Output is correct
17 Correct 17 ms 2152 KB Output is correct
18 Correct 18 ms 1960 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 0 ms 200 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 360 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 5 ms 584 KB Output is correct
9 Correct 8 ms 968 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 5 ms 840 KB Output is correct
12 Correct 8 ms 968 KB Output is correct
13 Correct 7 ms 968 KB Output is correct
14 Correct 9 ms 968 KB Output is correct
15 Correct 24 ms 2104 KB Output is correct
16 Correct 28 ms 2120 KB Output is correct
17 Correct 17 ms 2152 KB Output is correct
18 Correct 18 ms 1960 KB Output is correct
19 Correct 23 ms 2160 KB Output is correct
20 Correct 22 ms 2116 KB Output is correct
21 Correct 24 ms 2232 KB Output is correct
22 Correct 25 ms 2028 KB Output is correct

Subtask #6
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 0 ms 200 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 360 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 5 ms 584 KB Output is correct
9 Correct 8 ms 968 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 5 ms 840 KB Output is correct
12 Correct 8 ms 968 KB Output is correct
13 Correct 7 ms 968 KB Output is correct
14 Correct 9 ms 968 KB Output is correct
15 Correct 24 ms 2104 KB Output is correct
16 Correct 28 ms 2120 KB Output is correct
17 Correct 17 ms 2152 KB Output is correct
18 Correct 18 ms 1960 KB Output is correct
19 Correct 23 ms 2160 KB Output is correct
20 Correct 22 ms 2116 KB Output is correct
21 Correct 24 ms 2232 KB Output is correct
22 Correct 25 ms 2028 KB Output is correct
23 Incorrect 29 ms 1888 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #7
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 0 ms 200 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 360 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 5 ms 584 KB Output is correct
9 Correct 8 ms 968 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 5 ms 840 KB Output is correct
12 Correct 8 ms 968 KB Output is correct
13 Correct 7 ms 968 KB Output is correct
14 Correct 9 ms 968 KB Output is correct
15 Correct 24 ms 2104 KB Output is correct
16 Correct 28 ms 2120 KB Output is correct
17 Correct 17 ms 2152 KB Output is correct
18 Correct 18 ms 1960 KB Output is correct
19 Correct 23 ms 2160 KB Output is correct
20 Correct 22 ms 2116 KB Output is correct
21 Correct 24 ms 2232 KB Output is correct
22 Correct 25 ms 2028 KB Output is correct
23 Incorrect 29 ms 1888 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

Subtask #8
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 0 ms 200 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 360 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 5 ms 584 KB Output is correct
9 Correct 8 ms 968 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 5 ms 840 KB Output is correct
12 Correct 8 ms 968 KB Output is correct
13 Correct 7 ms 968 KB Output is correct
14 Correct 9 ms 968 KB Output is correct
15 Correct 24 ms 2104 KB Output is correct
16 Correct 28 ms 2120 KB Output is correct
17 Correct 17 ms 2152 KB Output is correct
18 Correct 18 ms 1960 KB Output is correct
19 Correct 23 ms 2160 KB Output is correct
20 Correct 22 ms 2116 KB Output is correct
21 Correct 24 ms 2232 KB Output is correct
22 Correct 25 ms 2028 KB Output is correct
23 Incorrect 29 ms 1888 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

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 0 ms 200 KB Output is correct
5 Correct 1 ms 328 KB Output is correct
6 Correct 1 ms 360 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 5 ms 584 KB Output is correct
9 Correct 8 ms 968 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 5 ms 840 KB Output is correct
12 Correct 8 ms 968 KB Output is correct
13 Correct 7 ms 968 KB Output is correct
14 Correct 9 ms 968 KB Output is correct
15 Correct 24 ms 2104 KB Output is correct
16 Correct 28 ms 2120 KB Output is correct
17 Correct 17 ms 2152 KB Output is correct
18 Correct 18 ms 1960 KB Output is correct
19 Correct 23 ms 2160 KB Output is correct
20 Correct 22 ms 2116 KB Output is correct
21 Correct 24 ms 2232 KB Output is correct
22 Correct 25 ms 2028 KB Output is correct
23 Incorrect 29 ms 1888 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -