oj.uz

Submission #772018

# Submission time Handle Problem Language Result Execution time Memory
772018 2023-07-03T14:08:39 Z doowey Minerals (JOI19_minerals) C++14
40 / 100
 313 ms 7420 KB 
#include <bits/stdc++.h>
#include "minerals.h"

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef long double ld;
#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)]);
    }
}

const ld golden = 0.63;

int split(int sz){
    return min((int)ceil((ld)sz * golden), sz - 1);
}

void pair_up(vector<int> A, vector<int> B, bool in_a, bool in_b){
    if(A.empty()) return;
    if(A.size() == 1){
        ans.push_back(mp(A[0], B[0]));
        return;
    }
    shuffle(A);
    shuffle(B);
    int mid = split(A.size());
    vector<int> a0, a1;
    bool ia0 = in_a, ia1 = in_a;
    bool ib0 = in_b, ib1 = in_b;
    vector<int> b0, b1;
    for(int i = 0 ; i < mid; i ++ ){
        int cur = ask(A[i]);
        las=cur;
        a0.push_back(A[i]);
    }
    ia0 ^= 1;
    for(int i = mid ; i < A.size(); i ++ ){
        a1.push_back(A[i]);
    }
    ib0 ^= 1;
    for(auto x : B){
        //if(A.size() <= 4){
            if(b0.size() == a0.size()){
                b1.push_back(x);
                continue;
            }
            else if(b1.size() == a1.size()){
                b0.push_back(x);
                continue;
            }

        //}
        int cur = ask(x);
        if(cur == las){
            if(ia0) b0.push_back(x);
            else b1.push_back(x);
        }
        else{
            if(ia0) b1.push_back(x);
            else b0.push_back(x);
        }
        las = cur;
    }
    pair_up(a0, b0, ia0, ib0);
    pair_up(a1, b1, ia1, ib1);
}


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, true);
    for (auto x : ans)
        Answer(x.fi, x.se);
}

Compilation message

minerals.cpp: In function 'void shuffle(std::vector<int>&)':
minerals.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for(int i = 0 ; i < ord.size(); i ++ ){
      |                     ~~^~~~~~~~~~~~
minerals.cpp: In function 'void pair_up(std::vector<int>, std::vector<int>, bool, bool)':
minerals.cpp:60:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     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 0 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 9 ms 660 KB Output is correct
3 Correct 20 ms 1020 KB Output is correct
4 Correct 47 ms 1744 KB Output is correct
5 Correct 102 ms 3080 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 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 9 ms 660 KB Output is correct
7 Correct 20 ms 1020 KB Output is correct
8 Correct 47 ms 1744 KB Output is correct
9 Correct 102 ms 3080 KB Output is correct
10 Correct 5 ms 464 KB Output is correct
11 Correct 64 ms 2084 KB Output is correct
12 Correct 106 ms 3156 KB Output is correct
13 Correct 99 ms 3104 KB Output is correct
14 Correct 102 ms 2964 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 0 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 9 ms 660 KB Output is correct
7 Correct 20 ms 1020 KB Output is correct
8 Correct 47 ms 1744 KB Output is correct
9 Correct 102 ms 3080 KB Output is correct
10 Correct 5 ms 464 KB Output is correct
11 Correct 64 ms 2084 KB Output is correct
12 Correct 106 ms 3156 KB Output is correct
13 Correct 99 ms 3104 KB Output is correct
14 Correct 102 ms 2964 KB Output is correct
15 Incorrect 313 ms 7420 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 0 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 9 ms 660 KB Output is correct
7 Correct 20 ms 1020 KB Output is correct
8 Correct 47 ms 1744 KB Output is correct
9 Correct 102 ms 3080 KB Output is correct
10 Correct 5 ms 464 KB Output is correct
11 Correct 64 ms 2084 KB Output is correct
12 Correct 106 ms 3156 KB Output is correct
13 Correct 99 ms 3104 KB Output is correct
14 Correct 102 ms 2964 KB Output is correct
15 Incorrect 313 ms 7420 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 0 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 9 ms 660 KB Output is correct
7 Correct 20 ms 1020 KB Output is correct
8 Correct 47 ms 1744 KB Output is correct
9 Correct 102 ms 3080 KB Output is correct
10 Correct 5 ms 464 KB Output is correct
11 Correct 64 ms 2084 KB Output is correct
12 Correct 106 ms 3156 KB Output is correct
13 Correct 99 ms 3104 KB Output is correct
14 Correct 102 ms 2964 KB Output is correct
15 Incorrect 313 ms 7420 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 0 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 9 ms 660 KB Output is correct
7 Correct 20 ms 1020 KB Output is correct
8 Correct 47 ms 1744 KB Output is correct
9 Correct 102 ms 3080 KB Output is correct
10 Correct 5 ms 464 KB Output is correct
11 Correct 64 ms 2084 KB Output is correct
12 Correct 106 ms 3156 KB Output is correct
13 Correct 99 ms 3104 KB Output is correct
14 Correct 102 ms 2964 KB Output is correct
15 Incorrect 313 ms 7420 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 0 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 9 ms 660 KB Output is correct
7 Correct 20 ms 1020 KB Output is correct
8 Correct 47 ms 1744 KB Output is correct
9 Correct 102 ms 3080 KB Output is correct
10 Correct 5 ms 464 KB Output is correct
11 Correct 64 ms 2084 KB Output is correct
12 Correct 106 ms 3156 KB Output is correct
13 Correct 99 ms 3104 KB Output is correct
14 Correct 102 ms 2964 KB Output is correct
15 Incorrect 313 ms 7420 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 0 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 9 ms 660 KB Output is correct
7 Correct 20 ms 1020 KB Output is correct
8 Correct 47 ms 1744 KB Output is correct
9 Correct 102 ms 3080 KB Output is correct
10 Correct 5 ms 464 KB Output is correct
11 Correct 64 ms 2084 KB Output is correct
12 Correct 106 ms 3156 KB Output is correct
13 Correct 99 ms 3104 KB Output is correct
14 Correct 102 ms 2964 KB Output is correct
15 Incorrect 313 ms 7420 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -