oj.uz

Submission #771945

# Submission time Handle Problem Language Result Execution time Memory
771945 2023-07-03T12:32:04 Z doowey Minerals (JOI19_minerals) C++17
40 / 100
 321 ms 7352 KB 
#include <bits/stdc++.h>
#include "minerals.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int gen(int m){
    return ((int)rng() % m + m) % m;
}

int las;
vector<pii> ans;
set<int> E;

int ask(int id){
    if(E.count(id)) E.erase(id);
    else E.insert(id);

    int res = Query(id);
    return res;
}

void shuffle(vector<int> &ord){
    for(int i = 0 ; i < ord.size(); i ++ ){
        swap(ord[i], ord[gen(i + 1)]);
    }
}


void pair_up(vector<int> A, vector<int> B, bool inq){
    if(A.empty()) return;
    if(A.size() == 1){
        ans.push_back(mp(A[0], B[0]));
        return;
    }
    shuffle(A);
    shuffle(B);
    int mid = (int)A.size() / 2;
    vector<int> a0, a1;
    vector<int> b0, b1;
    for(int i = 0 ; i < mid; i ++ ){
        int cur = ask(A[i]);
        las=cur;
        a0.push_back(A[i]);
    }
    for(int i = mid ; i < A.size(); i ++ ){
        a1.push_back(A[i]);
    }
    int cnt = 0;
    vector<int> take_out;
    for(auto x : B){
        if(!inq){
            if(b0.size() == a0.size()) {
                b1.push_back(x);
                continue;
            }
        }
        else{
            if(b0.size() == a1.size()){
                b1.push_back(x);
                continue;
            }
        }
        int cur = ask(x);
        if(cur == las){
            b0.push_back(x);
            cnt ++ ;
        }
        else{
            b1.push_back(x);
            take_out.push_back(x);
        }
        las=cur;
    }
    for(auto x : take_out){
        int cur = ask(x);
        las = cur;
    }
    if(inq)
        swap(b0,b1);
    pair_up(a0, b0, (inq ^ 1));
    pair_up(a1, b1, inq);
}


void Solve(int n) {
    las = 0;
    ans.clear();
    vector<int> ord;
    for(int i = 1; i <= 2 * n; i ++ ){
        ord.push_back(i);
    }
    shuffle(ord);
    vector<int> aa, bb;
    for(auto x : ord){
        int cur = ask(x);
        if(cur != las){
            aa.push_back(x);
        }
        else{
            bb.push_back(x);
        }
        las = cur;
    }
    pair_up(aa, bb, true);
    for (auto x : ans)
        Answer(x.fi, x.se);
}

Compilation message

minerals.cpp: In function 'void shuffle(std::vector<int>&)':
minerals.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i = 0 ; i < ord.size(); i ++ ){
      |                     ~~^~~~~~~~~~~~
minerals.cpp: In function 'void pair_up(std::vector<int>, std::vector<int>, bool)':
minerals.cpp:54:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |     for(int i = mid ; i < A.size(); i ++ ){
      |                       ~~^~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 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 4 ms 464 KB Output is correct
2 Correct 10 ms 668 KB Output is correct
3 Correct 21 ms 976 KB Output is correct
4 Correct 54 ms 1744 KB Output is correct
5 Correct 113 ms 3156 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 1 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 4 ms 464 KB Output is correct
6 Correct 10 ms 668 KB Output is correct
7 Correct 21 ms 976 KB Output is correct
8 Correct 54 ms 1744 KB Output is correct
9 Correct 113 ms 3156 KB Output is correct
10 Correct 4 ms 380 KB Output is correct
11 Correct 71 ms 2312 KB Output is correct
12 Correct 122 ms 3204 KB Output is correct
13 Correct 119 ms 3140 KB Output is correct
14 Correct 111 ms 3160 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 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 4 ms 464 KB Output is correct
6 Correct 10 ms 668 KB Output is correct
7 Correct 21 ms 976 KB Output is correct
8 Correct 54 ms 1744 KB Output is correct
9 Correct 113 ms 3156 KB Output is correct
10 Correct 4 ms 380 KB Output is correct
11 Correct 71 ms 2312 KB Output is correct
12 Correct 122 ms 3204 KB Output is correct
13 Correct 119 ms 3140 KB Output is correct
14 Correct 111 ms 3160 KB Output is correct
15 Incorrect 321 ms 7352 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 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 4 ms 464 KB Output is correct
6 Correct 10 ms 668 KB Output is correct
7 Correct 21 ms 976 KB Output is correct
8 Correct 54 ms 1744 KB Output is correct
9 Correct 113 ms 3156 KB Output is correct
10 Correct 4 ms 380 KB Output is correct
11 Correct 71 ms 2312 KB Output is correct
12 Correct 122 ms 3204 KB Output is correct
13 Correct 119 ms 3140 KB Output is correct
14 Correct 111 ms 3160 KB Output is correct
15 Incorrect 321 ms 7352 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 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 4 ms 464 KB Output is correct
6 Correct 10 ms 668 KB Output is correct
7 Correct 21 ms 976 KB Output is correct
8 Correct 54 ms 1744 KB Output is correct
9 Correct 113 ms 3156 KB Output is correct
10 Correct 4 ms 380 KB Output is correct
11 Correct 71 ms 2312 KB Output is correct
12 Correct 122 ms 3204 KB Output is correct
13 Correct 119 ms 3140 KB Output is correct
14 Correct 111 ms 3160 KB Output is correct
15 Incorrect 321 ms 7352 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 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 4 ms 464 KB Output is correct
6 Correct 10 ms 668 KB Output is correct
7 Correct 21 ms 976 KB Output is correct
8 Correct 54 ms 1744 KB Output is correct
9 Correct 113 ms 3156 KB Output is correct
10 Correct 4 ms 380 KB Output is correct
11 Correct 71 ms 2312 KB Output is correct
12 Correct 122 ms 3204 KB Output is correct
13 Correct 119 ms 3140 KB Output is correct
14 Correct 111 ms 3160 KB Output is correct
15 Incorrect 321 ms 7352 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 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 4 ms 464 KB Output is correct
6 Correct 10 ms 668 KB Output is correct
7 Correct 21 ms 976 KB Output is correct
8 Correct 54 ms 1744 KB Output is correct
9 Correct 113 ms 3156 KB Output is correct
10 Correct 4 ms 380 KB Output is correct
11 Correct 71 ms 2312 KB Output is correct
12 Correct 122 ms 3204 KB Output is correct
13 Correct 119 ms 3140 KB Output is correct
14 Correct 111 ms 3160 KB Output is correct
15 Incorrect 321 ms 7352 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 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 4 ms 464 KB Output is correct
6 Correct 10 ms 668 KB Output is correct
7 Correct 21 ms 976 KB Output is correct
8 Correct 54 ms 1744 KB Output is correct
9 Correct 113 ms 3156 KB Output is correct
10 Correct 4 ms 380 KB Output is correct
11 Correct 71 ms 2312 KB Output is correct
12 Correct 122 ms 3204 KB Output is correct
13 Correct 119 ms 3140 KB Output is correct
14 Correct 111 ms 3160 KB Output is correct
15 Incorrect 321 ms 7352 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -