oj.uz

답안 #771946

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
771946 2023-07-03T12:32:17 Z doowey Minerals (JOI19_minerals) C++14
40 / 100
 48 ms 3856 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, 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: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>, bool)':
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

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 3 ms 464 KB Output is correct
3 Correct 5 ms 592 KB Output is correct
4 Correct 10 ms 996 KB Output is correct
5 Correct 20 ms 1660 KB Output is correct

Subtask #3
9.0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 464 KB Output is correct
7 Correct 5 ms 592 KB Output is correct
8 Correct 10 ms 996 KB Output is correct
9 Correct 20 ms 1660 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 14 ms 1440 KB Output is correct
12 Correct 21 ms 1732 KB Output is correct
13 Correct 21 ms 1744 KB Output is correct
14 Correct 22 ms 1684 KB Output is correct

Subtask #4
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 464 KB Output is correct
7 Correct 5 ms 592 KB Output is correct
8 Correct 10 ms 996 KB Output is correct
9 Correct 20 ms 1660 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 14 ms 1440 KB Output is correct
12 Correct 21 ms 1732 KB Output is correct
13 Correct 21 ms 1744 KB Output is correct
14 Correct 22 ms 1684 KB Output is correct
15 Incorrect 48 ms 3856 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 464 KB Output is correct
7 Correct 5 ms 592 KB Output is correct
8 Correct 10 ms 996 KB Output is correct
9 Correct 20 ms 1660 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 14 ms 1440 KB Output is correct
12 Correct 21 ms 1732 KB Output is correct
13 Correct 21 ms 1744 KB Output is correct
14 Correct 22 ms 1684 KB Output is correct
15 Incorrect 48 ms 3856 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 464 KB Output is correct
7 Correct 5 ms 592 KB Output is correct
8 Correct 10 ms 996 KB Output is correct
9 Correct 20 ms 1660 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 14 ms 1440 KB Output is correct
12 Correct 21 ms 1732 KB Output is correct
13 Correct 21 ms 1744 KB Output is correct
14 Correct 22 ms 1684 KB Output is correct
15 Incorrect 48 ms 3856 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 464 KB Output is correct
7 Correct 5 ms 592 KB Output is correct
8 Correct 10 ms 996 KB Output is correct
9 Correct 20 ms 1660 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 14 ms 1440 KB Output is correct
12 Correct 21 ms 1732 KB Output is correct
13 Correct 21 ms 1744 KB Output is correct
14 Correct 22 ms 1684 KB Output is correct
15 Incorrect 48 ms 3856 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 464 KB Output is correct
7 Correct 5 ms 592 KB Output is correct
8 Correct 10 ms 996 KB Output is correct
9 Correct 20 ms 1660 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 14 ms 1440 KB Output is correct
12 Correct 21 ms 1732 KB Output is correct
13 Correct 21 ms 1744 KB Output is correct
14 Correct 22 ms 1684 KB Output is correct
15 Incorrect 48 ms 3856 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 0 ms 208 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 3 ms 464 KB Output is correct
7 Correct 5 ms 592 KB Output is correct
8 Correct 10 ms 996 KB Output is correct
9 Correct 20 ms 1660 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 14 ms 1440 KB Output is correct
12 Correct 21 ms 1732 KB Output is correct
13 Correct 21 ms 1744 KB Output is correct
14 Correct 22 ms 1684 KB Output is correct
15 Incorrect 48 ms 3856 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -