oj.uz

Submission #489308

# Submission time Handle Problem Language Result Execution time Memory
489308 2021-11-22T08:48:34 Z balbit Minerals (JOI19_minerals) C++14
70 / 100
 26 ms 2212 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 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;

    REP(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:87:10: warning: unused variable 'inside' [-Wunused-variable]
   87 |     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 0 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 328 KB Output is correct
3 Correct 2 ms 456 KB Output is correct
4 Correct 6 ms 584 KB Output is correct
5 Correct 9 ms 932 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 0 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 328 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 6 ms 584 KB Output is correct
9 Correct 9 ms 932 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 5 ms 712 KB Output is correct
12 Correct 8 ms 968 KB Output is correct
13 Correct 8 ms 960 KB Output is correct
14 Correct 9 ms 880 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 0 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 328 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 6 ms 584 KB Output is correct
9 Correct 9 ms 932 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 5 ms 712 KB Output is correct
12 Correct 8 ms 968 KB Output is correct
13 Correct 8 ms 960 KB Output is correct
14 Correct 9 ms 880 KB Output is correct
15 Correct 26 ms 2120 KB Output is correct
16 Correct 23 ms 2108 KB Output is correct
17 Correct 23 ms 2212 KB Output is correct
18 Correct 18 ms 1972 KB Output is correct

Subtask #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 0 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 328 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 6 ms 584 KB Output is correct
9 Correct 9 ms 932 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 5 ms 712 KB Output is correct
12 Correct 8 ms 968 KB Output is correct
13 Correct 8 ms 960 KB Output is correct
14 Correct 9 ms 880 KB Output is correct
15 Correct 26 ms 2120 KB Output is correct
16 Correct 23 ms 2108 KB Output is correct
17 Correct 23 ms 2212 KB Output is correct
18 Correct 18 ms 1972 KB Output is correct
19 Incorrect 21 ms 1896 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -

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 0 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 328 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 6 ms 584 KB Output is correct
9 Correct 9 ms 932 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 5 ms 712 KB Output is correct
12 Correct 8 ms 968 KB Output is correct
13 Correct 8 ms 960 KB Output is correct
14 Correct 9 ms 880 KB Output is correct
15 Correct 26 ms 2120 KB Output is correct
16 Correct 23 ms 2108 KB Output is correct
17 Correct 23 ms 2212 KB Output is correct
18 Correct 18 ms 1972 KB Output is correct
19 Incorrect 21 ms 1896 KB Wrong Answer [2]
20 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 0 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 328 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 6 ms 584 KB Output is correct
9 Correct 9 ms 932 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 5 ms 712 KB Output is correct
12 Correct 8 ms 968 KB Output is correct
13 Correct 8 ms 960 KB Output is correct
14 Correct 9 ms 880 KB Output is correct
15 Correct 26 ms 2120 KB Output is correct
16 Correct 23 ms 2108 KB Output is correct
17 Correct 23 ms 2212 KB Output is correct
18 Correct 18 ms 1972 KB Output is correct
19 Incorrect 21 ms 1896 KB Wrong Answer [2]
20 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 0 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 328 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 6 ms 584 KB Output is correct
9 Correct 9 ms 932 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 5 ms 712 KB Output is correct
12 Correct 8 ms 968 KB Output is correct
13 Correct 8 ms 960 KB Output is correct
14 Correct 9 ms 880 KB Output is correct
15 Correct 26 ms 2120 KB Output is correct
16 Correct 23 ms 2108 KB Output is correct
17 Correct 23 ms 2212 KB Output is correct
18 Correct 18 ms 1972 KB Output is correct
19 Incorrect 21 ms 1896 KB Wrong Answer [2]
20 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 0 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 328 KB Output is correct
7 Correct 2 ms 456 KB Output is correct
8 Correct 6 ms 584 KB Output is correct
9 Correct 9 ms 932 KB Output is correct
10 Correct 1 ms 328 KB Output is correct
11 Correct 5 ms 712 KB Output is correct
12 Correct 8 ms 968 KB Output is correct
13 Correct 8 ms 960 KB Output is correct
14 Correct 9 ms 880 KB Output is correct
15 Correct 26 ms 2120 KB Output is correct
16 Correct 23 ms 2108 KB Output is correct
17 Correct 23 ms 2212 KB Output is correct
18 Correct 18 ms 1972 KB Output is correct
19 Incorrect 21 ms 1896 KB Wrong Answer [2]
20 Halted 0 ms 0 KB -