oj.uz

Submission #203339

# Submission time Handle Problem Language Result Execution time Memory
203339 2020-02-20T09:09:16 Z theStaticMind Minerals (JOI19_minerals) C++14
75 / 100
 312 ms 6052 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]))){
            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;

      for(int i = 1; i <= 2 * N; i++){
            int 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:46: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 248 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 18 ms 632 KB Output is correct
3 Correct 26 ms 888 KB Output is correct
4 Correct 44 ms 1400 KB Output is correct
5 Correct 102 ms 2296 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 248 KB Output is correct
5 Correct 9 ms 376 KB Output is correct
6 Correct 18 ms 632 KB Output is correct
7 Correct 26 ms 888 KB Output is correct
8 Correct 44 ms 1400 KB Output is correct
9 Correct 102 ms 2296 KB Output is correct
10 Correct 9 ms 504 KB Output is correct
11 Correct 68 ms 1656 KB Output is correct
12 Correct 107 ms 2424 KB Output is correct
13 Correct 85 ms 2428 KB Output is correct
14 Correct 78 ms 2296 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 248 KB Output is correct
5 Correct 9 ms 376 KB Output is correct
6 Correct 18 ms 632 KB Output is correct
7 Correct 26 ms 888 KB Output is correct
8 Correct 44 ms 1400 KB Output is correct
9 Correct 102 ms 2296 KB Output is correct
10 Correct 9 ms 504 KB Output is correct
11 Correct 68 ms 1656 KB Output is correct
12 Correct 107 ms 2424 KB Output is correct
13 Correct 85 ms 2428 KB Output is correct
14 Correct 78 ms 2296 KB Output is correct
15 Correct 297 ms 5800 KB Output is correct
16 Correct 287 ms 5876 KB Output is correct
17 Correct 218 ms 5744 KB Output is correct
18 Correct 203 ms 5616 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 248 KB Output is correct
5 Correct 9 ms 376 KB Output is correct
6 Correct 18 ms 632 KB Output is correct
7 Correct 26 ms 888 KB Output is correct
8 Correct 44 ms 1400 KB Output is correct
9 Correct 102 ms 2296 KB Output is correct
10 Correct 9 ms 504 KB Output is correct
11 Correct 68 ms 1656 KB Output is correct
12 Correct 107 ms 2424 KB Output is correct
13 Correct 85 ms 2428 KB Output is correct
14 Correct 78 ms 2296 KB Output is correct
15 Correct 297 ms 5800 KB Output is correct
16 Correct 287 ms 5876 KB Output is correct
17 Correct 218 ms 5744 KB Output is correct
18 Correct 203 ms 5616 KB Output is correct
19 Correct 301 ms 5924 KB Output is correct
20 Correct 298 ms 5748 KB Output is correct
21 Correct 229 ms 6052 KB Output is correct
22 Correct 218 ms 5748 KB Output is correct

Subtask #6
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 248 KB Output is correct
5 Correct 9 ms 376 KB Output is correct
6 Correct 18 ms 632 KB Output is correct
7 Correct 26 ms 888 KB Output is correct
8 Correct 44 ms 1400 KB Output is correct
9 Correct 102 ms 2296 KB Output is correct
10 Correct 9 ms 504 KB Output is correct
11 Correct 68 ms 1656 KB Output is correct
12 Correct 107 ms 2424 KB Output is correct
13 Correct 85 ms 2428 KB Output is correct
14 Correct 78 ms 2296 KB Output is correct
15 Correct 297 ms 5800 KB Output is correct
16 Correct 287 ms 5876 KB Output is correct
17 Correct 218 ms 5744 KB Output is correct
18 Correct 203 ms 5616 KB Output is correct
19 Correct 301 ms 5924 KB Output is correct
20 Correct 298 ms 5748 KB Output is correct
21 Correct 229 ms 6052 KB Output is correct
22 Correct 218 ms 5748 KB Output is correct
23 Incorrect 312 ms 6004 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -

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 248 KB Output is correct
5 Correct 9 ms 376 KB Output is correct
6 Correct 18 ms 632 KB Output is correct
7 Correct 26 ms 888 KB Output is correct
8 Correct 44 ms 1400 KB Output is correct
9 Correct 102 ms 2296 KB Output is correct
10 Correct 9 ms 504 KB Output is correct
11 Correct 68 ms 1656 KB Output is correct
12 Correct 107 ms 2424 KB Output is correct
13 Correct 85 ms 2428 KB Output is correct
14 Correct 78 ms 2296 KB Output is correct
15 Correct 297 ms 5800 KB Output is correct
16 Correct 287 ms 5876 KB Output is correct
17 Correct 218 ms 5744 KB Output is correct
18 Correct 203 ms 5616 KB Output is correct
19 Correct 301 ms 5924 KB Output is correct
20 Correct 298 ms 5748 KB Output is correct
21 Correct 229 ms 6052 KB Output is correct
22 Correct 218 ms 5748 KB Output is correct
23 Incorrect 312 ms 6004 KB Wrong Answer [2]
24 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 248 KB Output is correct
5 Correct 9 ms 376 KB Output is correct
6 Correct 18 ms 632 KB Output is correct
7 Correct 26 ms 888 KB Output is correct
8 Correct 44 ms 1400 KB Output is correct
9 Correct 102 ms 2296 KB Output is correct
10 Correct 9 ms 504 KB Output is correct
11 Correct 68 ms 1656 KB Output is correct
12 Correct 107 ms 2424 KB Output is correct
13 Correct 85 ms 2428 KB Output is correct
14 Correct 78 ms 2296 KB Output is correct
15 Correct 297 ms 5800 KB Output is correct
16 Correct 287 ms 5876 KB Output is correct
17 Correct 218 ms 5744 KB Output is correct
18 Correct 203 ms 5616 KB Output is correct
19 Correct 301 ms 5924 KB Output is correct
20 Correct 298 ms 5748 KB Output is correct
21 Correct 229 ms 6052 KB Output is correct
22 Correct 218 ms 5748 KB Output is correct
23 Incorrect 312 ms 6004 KB Wrong Answer [2]
24 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 248 KB Output is correct
5 Correct 9 ms 376 KB Output is correct
6 Correct 18 ms 632 KB Output is correct
7 Correct 26 ms 888 KB Output is correct
8 Correct 44 ms 1400 KB Output is correct
9 Correct 102 ms 2296 KB Output is correct
10 Correct 9 ms 504 KB Output is correct
11 Correct 68 ms 1656 KB Output is correct
12 Correct 107 ms 2424 KB Output is correct
13 Correct 85 ms 2428 KB Output is correct
14 Correct 78 ms 2296 KB Output is correct
15 Correct 297 ms 5800 KB Output is correct
16 Correct 287 ms 5876 KB Output is correct
17 Correct 218 ms 5744 KB Output is correct
18 Correct 203 ms 5616 KB Output is correct
19 Correct 301 ms 5924 KB Output is correct
20 Correct 298 ms 5748 KB Output is correct
21 Correct 229 ms 6052 KB Output is correct
22 Correct 218 ms 5748 KB Output is correct
23 Incorrect 312 ms 6004 KB Wrong Answer [2]
24 Halted 0 ms 0 KB -