oj.uz

Submission #771903

# Submission time Handle Problem Language Result Execution time Memory
771903 2023-07-03T11:39:32 Z doowey Minerals (JOI19_minerals) C++14
40 / 100
 39 ms 3564 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;

int ask(int 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){
    if(A.empty()) return;
    if(A.size() == 1){
        ans.push_back(mp(A[0], B[0]));
        return;
    }
    shuffle(A);
    shuffle(B);
    int mid = 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;
    for(auto x : B){
        if(cnt == mid){
            b1.push_back(x);
        }
        else{
            int cur = ask(x);
            if(cur == las){
                b0.push_back(x);
                cnt ++ ;
            }
            else{
                b1.push_back(x);
            }
            las=cur;
        }
    }
    for(auto x : a0){
        ask(x);
    }
    for(auto x : b0){
        ask(x);
    }
    las = 0;
    pair_up(a0, b0);
    pair_up(a1, b1);
}


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;
    }
    for(auto x : ord){
        int cur = ask(x);
        las = cur;
    }
    pair_up(aa, bb);
    for (auto x : ans)
        Answer(x.fi, x.se);
}

Compilation message

minerals.cpp: In function 'void shuffle(std::vector<int>&)':
minerals.cpp:28:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i = 0 ; i < ord.size(); i ++ ){
      |                     ~~^~~~~~~~~~~~
minerals.cpp: In function 'void pair_up(std::vector<int>, std::vector<int>)':
minerals.cpp:50:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     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 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 2 ms 464 KB Output is correct
3 Correct 5 ms 652 KB Output is correct
4 Correct 10 ms 1044 KB Output is correct
5 Correct 20 ms 1616 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 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 5 ms 652 KB Output is correct
8 Correct 10 ms 1044 KB Output is correct
9 Correct 20 ms 1616 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 13 ms 1388 KB Output is correct
12 Correct 20 ms 1764 KB Output is correct
13 Correct 20 ms 1764 KB Output is correct
14 Correct 24 ms 1616 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 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 5 ms 652 KB Output is correct
8 Correct 10 ms 1044 KB Output is correct
9 Correct 20 ms 1616 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 13 ms 1388 KB Output is correct
12 Correct 20 ms 1764 KB Output is correct
13 Correct 20 ms 1764 KB Output is correct
14 Correct 24 ms 1616 KB Output is correct
15 Incorrect 39 ms 3564 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 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 5 ms 652 KB Output is correct
8 Correct 10 ms 1044 KB Output is correct
9 Correct 20 ms 1616 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 13 ms 1388 KB Output is correct
12 Correct 20 ms 1764 KB Output is correct
13 Correct 20 ms 1764 KB Output is correct
14 Correct 24 ms 1616 KB Output is correct
15 Incorrect 39 ms 3564 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 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 5 ms 652 KB Output is correct
8 Correct 10 ms 1044 KB Output is correct
9 Correct 20 ms 1616 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 13 ms 1388 KB Output is correct
12 Correct 20 ms 1764 KB Output is correct
13 Correct 20 ms 1764 KB Output is correct
14 Correct 24 ms 1616 KB Output is correct
15 Incorrect 39 ms 3564 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 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 5 ms 652 KB Output is correct
8 Correct 10 ms 1044 KB Output is correct
9 Correct 20 ms 1616 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 13 ms 1388 KB Output is correct
12 Correct 20 ms 1764 KB Output is correct
13 Correct 20 ms 1764 KB Output is correct
14 Correct 24 ms 1616 KB Output is correct
15 Incorrect 39 ms 3564 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 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 5 ms 652 KB Output is correct
8 Correct 10 ms 1044 KB Output is correct
9 Correct 20 ms 1616 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 13 ms 1388 KB Output is correct
12 Correct 20 ms 1764 KB Output is correct
13 Correct 20 ms 1764 KB Output is correct
14 Correct 24 ms 1616 KB Output is correct
15 Incorrect 39 ms 3564 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 0 ms 208 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 2 ms 464 KB Output is correct
7 Correct 5 ms 652 KB Output is correct
8 Correct 10 ms 1044 KB Output is correct
9 Correct 20 ms 1616 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 13 ms 1388 KB Output is correct
12 Correct 20 ms 1764 KB Output is correct
13 Correct 20 ms 1764 KB Output is correct
14 Correct 24 ms 1616 KB Output is correct
15 Incorrect 39 ms 3564 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -