oj.uz

Submission #203343

# Submission time Handle Problem Language Result Execution time Memory
203343 2020-02-20T09:18:55 Z theStaticMind Minerals (JOI19_minerals) C++14
80 / 100
 443 ms 6564 KB 
#include<bits/stdc++.h>
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define INF 1000000000//00000000
#define modulo 1000000007
#define mod 998244353
//#define int long long int
using namespace std;

#include "minerals.h"

int last = 0;
set<int> S;

void add(int x){
      if(S.count(x))S.erase(x);
      else S.insert(x);
}

void extract(vector<int>& A, vector<int>& B, vector<int>& X, vector<int>& Y){
      int n = sz(A), m = sz(B);
      for(int i = 0; i < m; i++){
            int v = Query(B[i]);
            add(B[i]);
            if(v == last){
                  X.pb(B[i]);
            }
            else Y.pb(B[i]);
            last = v;
      }
}

void divide(vector<int>& A, vector<int>& B){
      int n = A.size();
      if(n == 1){
            Answer(A[0], B[0]);
            return;
      }
      vector<int> X, Y;
      vector<int> tempA, tempB;
      for(int i = 0; i < n / 2; i++)tempA.pb(A[i]);
      for(int i = n / 2; i < n; i++)tempB.pb(A[i]);
      if(!(S.count(tempA[0]) ^ S.count(tempB[0]))){
            if(tempB.size() > tempA.size()) swap(tempA, tempB);
            for(int i = 0; i < tempB.size(); i++) last = Query(tempB[i]), add(tempB[i]);
      }
      if(S.count(tempB[0])){
            swap(tempA, tempB);
      }
      extract(tempA, B, X, Y);
      divide(tempA, X);
      divide(tempB, Y);
}

void Solve(int N) {
      vector<int> A, B;
      vector<int> arr;
      for(int i = 1; i <= 2 * N; i++)arr.pb(i);
      srand(time(NULL));
      for(int i = 0; i < 2 * N; i++) swap(arr[rand() % sz(arr)], arr[rand() % sz(arr)]);
      for(auto i : arr){
            int q;
            if(last == N) q = last;
            else q = Query(i);
            S.insert(i);
            if(last == q){
                  B.pb(i);
            }
            else{
                  A.pb(i);
            }
            last = q;
      }
      divide(A, B);
}

Compilation message

minerals.cpp: In function 'void extract(std::vector<int>&, std::vector<int>&, std::vector<int>&, std::vector<int>&)':
minerals.cpp:23:11: warning: unused variable 'n' [-Wunused-variable]
       int n = sz(A), m = sz(B);
           ^
minerals.cpp: In function 'void divide(std::vector<int>&, std::vector<int>&)':
minerals.cpp:47:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < tempB.size(); i++) last = Query(tempB[i]), add(tempB[i]);
                            ~~^~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 248 KB Output is correct
4 Correct 5 ms 376 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 376 KB Output is correct
2 Correct 16 ms 632 KB Output is correct
3 Correct 30 ms 888 KB Output is correct
4 Correct 60 ms 1488 KB Output is correct
5 Correct 135 ms 2552 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 248 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 9 ms 376 KB Output is correct
6 Correct 16 ms 632 KB Output is correct
7 Correct 30 ms 888 KB Output is correct
8 Correct 60 ms 1488 KB Output is correct
9 Correct 135 ms 2552 KB Output is correct
10 Correct 10 ms 504 KB Output is correct
11 Correct 82 ms 1784 KB Output is correct
12 Correct 135 ms 2572 KB Output is correct
13 Correct 136 ms 2680 KB Output is correct
14 Correct 144 ms 2424 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 248 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 9 ms 376 KB Output is correct
6 Correct 16 ms 632 KB Output is correct
7 Correct 30 ms 888 KB Output is correct
8 Correct 60 ms 1488 KB Output is correct
9 Correct 135 ms 2552 KB Output is correct
10 Correct 10 ms 504 KB Output is correct
11 Correct 82 ms 1784 KB Output is correct
12 Correct 135 ms 2572 KB Output is correct
13 Correct 136 ms 2680 KB Output is correct
14 Correct 144 ms 2424 KB Output is correct
15 Correct 393 ms 5924 KB Output is correct
16 Correct 419 ms 6000 KB Output is correct
17 Correct 386 ms 5872 KB Output is correct
18 Correct 413 ms 5868 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 248 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 9 ms 376 KB Output is correct
6 Correct 16 ms 632 KB Output is correct
7 Correct 30 ms 888 KB Output is correct
8 Correct 60 ms 1488 KB Output is correct
9 Correct 135 ms 2552 KB Output is correct
10 Correct 10 ms 504 KB Output is correct
11 Correct 82 ms 1784 KB Output is correct
12 Correct 135 ms 2572 KB Output is correct
13 Correct 136 ms 2680 KB Output is correct
14 Correct 144 ms 2424 KB Output is correct
15 Correct 393 ms 5924 KB Output is correct
16 Correct 419 ms 6000 KB Output is correct
17 Correct 386 ms 5872 KB Output is correct
18 Correct 413 ms 5868 KB Output is correct
19 Correct 416 ms 6056 KB Output is correct
20 Correct 432 ms 6128 KB Output is correct
21 Correct 418 ms 6124 KB Output is correct
22 Correct 406 ms 5872 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 248 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 9 ms 376 KB Output is correct
6 Correct 16 ms 632 KB Output is correct
7 Correct 30 ms 888 KB Output is correct
8 Correct 60 ms 1488 KB Output is correct
9 Correct 135 ms 2552 KB Output is correct
10 Correct 10 ms 504 KB Output is correct
11 Correct 82 ms 1784 KB Output is correct
12 Correct 135 ms 2572 KB Output is correct
13 Correct 136 ms 2680 KB Output is correct
14 Correct 144 ms 2424 KB Output is correct
15 Correct 393 ms 5924 KB Output is correct
16 Correct 419 ms 6000 KB Output is correct
17 Correct 386 ms 5872 KB Output is correct
18 Correct 413 ms 5868 KB Output is correct
19 Correct 416 ms 6056 KB Output is correct
20 Correct 432 ms 6128 KB Output is correct
21 Correct 418 ms 6124 KB Output is correct
22 Correct 406 ms 5872 KB Output is correct
23 Correct 432 ms 6256 KB Output is correct
24 Correct 421 ms 6256 KB Output is correct
25 Correct 443 ms 6256 KB Output is correct
26 Correct 425 ms 6128 KB Output is correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 248 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 9 ms 376 KB Output is correct
6 Correct 16 ms 632 KB Output is correct
7 Correct 30 ms 888 KB Output is correct
8 Correct 60 ms 1488 KB Output is correct
9 Correct 135 ms 2552 KB Output is correct
10 Correct 10 ms 504 KB Output is correct
11 Correct 82 ms 1784 KB Output is correct
12 Correct 135 ms 2572 KB Output is correct
13 Correct 136 ms 2680 KB Output is correct
14 Correct 144 ms 2424 KB Output is correct
15 Correct 393 ms 5924 KB Output is correct
16 Correct 419 ms 6000 KB Output is correct
17 Correct 386 ms 5872 KB Output is correct
18 Correct 413 ms 5868 KB Output is correct
19 Correct 416 ms 6056 KB Output is correct
20 Correct 432 ms 6128 KB Output is correct
21 Correct 418 ms 6124 KB Output is correct
22 Correct 406 ms 5872 KB Output is correct
23 Correct 432 ms 6256 KB Output is correct
24 Correct 421 ms 6256 KB Output is correct
25 Correct 443 ms 6256 KB Output is correct
26 Correct 425 ms 6128 KB Output is correct
27 Incorrect 437 ms 6564 KB Wrong Answer [2]
28 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 248 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 9 ms 376 KB Output is correct
6 Correct 16 ms 632 KB Output is correct
7 Correct 30 ms 888 KB Output is correct
8 Correct 60 ms 1488 KB Output is correct
9 Correct 135 ms 2552 KB Output is correct
10 Correct 10 ms 504 KB Output is correct
11 Correct 82 ms 1784 KB Output is correct
12 Correct 135 ms 2572 KB Output is correct
13 Correct 136 ms 2680 KB Output is correct
14 Correct 144 ms 2424 KB Output is correct
15 Correct 393 ms 5924 KB Output is correct
16 Correct 419 ms 6000 KB Output is correct
17 Correct 386 ms 5872 KB Output is correct
18 Correct 413 ms 5868 KB Output is correct
19 Correct 416 ms 6056 KB Output is correct
20 Correct 432 ms 6128 KB Output is correct
21 Correct 418 ms 6124 KB Output is correct
22 Correct 406 ms 5872 KB Output is correct
23 Correct 432 ms 6256 KB Output is correct
24 Correct 421 ms 6256 KB Output is correct
25 Correct 443 ms 6256 KB Output is correct
26 Correct 425 ms 6128 KB Output is correct
27 Incorrect 437 ms 6564 KB Wrong Answer [2]
28 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 248 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 248 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 9 ms 376 KB Output is correct
6 Correct 16 ms 632 KB Output is correct
7 Correct 30 ms 888 KB Output is correct
8 Correct 60 ms 1488 KB Output is correct
9 Correct 135 ms 2552 KB Output is correct
10 Correct 10 ms 504 KB Output is correct
11 Correct 82 ms 1784 KB Output is correct
12 Correct 135 ms 2572 KB Output is correct
13 Correct 136 ms 2680 KB Output is correct
14 Correct 144 ms 2424 KB Output is correct
15 Correct 393 ms 5924 KB Output is correct
16 Correct 419 ms 6000 KB Output is correct
17 Correct 386 ms 5872 KB Output is correct
18 Correct 413 ms 5868 KB Output is correct
19 Correct 416 ms 6056 KB Output is correct
20 Correct 432 ms 6128 KB Output is correct
21 Correct 418 ms 6124 KB Output is correct
22 Correct 406 ms 5872 KB Output is correct
23 Correct 432 ms 6256 KB Output is correct
24 Correct 421 ms 6256 KB Output is correct
25 Correct 443 ms 6256 KB Output is correct
26 Correct 425 ms 6128 KB Output is correct
27 Incorrect 437 ms 6564 KB Wrong Answer [2]
28 Halted 0 ms 0 KB -