oj.uz

Submission #112356

# Submission time Handle Problem Language Result Execution time Memory
112356 2019-05-19T03:46:50 Z shoemakerjo Minerals (JOI19_minerals) C++14
40 / 100
 284 ms 6108 KB 
#include "minerals.h"
#include <bits/stdc++.h>

using namespace std;

int nmask[45000];
map<int, int> v;

map<int, int> ccount;

mt19937 mt_rand(time(NULL));

void Solve(int N) {
  // int nrounds = 1000000/N;
  int pguy = 0;

  //throw me out if I am completely alone in my mask

  set<int> curin;
  vector<int> stuff;
  for (int i = 1; i <= 2*N; i++) {
    curin.insert(i);
  }
  int nc = 0;
  int pres = 0;
  while (curin.size()) {
    ++nc;
    stuff.clear();
    for (int v : curin) {
      stuff.push_back(v);
    }
    shuffle(stuff.begin(), stuff.end(), mt_rand);
    ccount.clear();
    v.clear();
    for (int vv : stuff) {
      nmask[vv] *= 2;
      int cur = Query(vv);
      if (cur != pres) {
        nmask[vv]++;
        pres = cur;
      }
      ccount[nmask[vv]]++;
      v[nmask[vv]] = vv;

      // cout << vv << " : " << nmask[vv] << endl;
    }

    for (int vv : stuff) {
      if (ccount[nmask[vv]] > 1) continue;
      int omask =  nmask[vv] ^ ((1 << nc)-1);
      if (nmask[vv] < omask) continue;
      int og = v[omask];
      // cout << vv << " and " << og << endl;
      Answer(vv, og);
      curin.erase(curin.find(vv));
      curin.erase(curin.find(og));
    }
  }
}

Compilation message

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:15:7: warning: unused variable 'pguy' [-Wunused-variable]
   int pguy = 0;
       ^~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 512 KB Output is correct
2 Correct 14 ms 688 KB Output is correct
3 Correct 33 ms 1152 KB Output is correct
4 Correct 82 ms 1968 KB Output is correct
5 Correct 198 ms 3544 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 7 ms 512 KB Output is correct
6 Correct 14 ms 688 KB Output is correct
7 Correct 33 ms 1152 KB Output is correct
8 Correct 82 ms 1968 KB Output is correct
9 Correct 198 ms 3544 KB Output is correct
10 Correct 7 ms 512 KB Output is correct
11 Correct 111 ms 2552 KB Output is correct
12 Correct 193 ms 3704 KB Output is correct
13 Correct 200 ms 3720 KB Output is correct
14 Correct 199 ms 3512 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 7 ms 512 KB Output is correct
6 Correct 14 ms 688 KB Output is correct
7 Correct 33 ms 1152 KB Output is correct
8 Correct 82 ms 1968 KB Output is correct
9 Correct 198 ms 3544 KB Output is correct
10 Correct 7 ms 512 KB Output is correct
11 Correct 111 ms 2552 KB Output is correct
12 Correct 193 ms 3704 KB Output is correct
13 Correct 200 ms 3720 KB Output is correct
14 Correct 199 ms 3512 KB Output is correct
15 Incorrect 284 ms 6108 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 7 ms 512 KB Output is correct
6 Correct 14 ms 688 KB Output is correct
7 Correct 33 ms 1152 KB Output is correct
8 Correct 82 ms 1968 KB Output is correct
9 Correct 198 ms 3544 KB Output is correct
10 Correct 7 ms 512 KB Output is correct
11 Correct 111 ms 2552 KB Output is correct
12 Correct 193 ms 3704 KB Output is correct
13 Correct 200 ms 3720 KB Output is correct
14 Correct 199 ms 3512 KB Output is correct
15 Incorrect 284 ms 6108 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 7 ms 512 KB Output is correct
6 Correct 14 ms 688 KB Output is correct
7 Correct 33 ms 1152 KB Output is correct
8 Correct 82 ms 1968 KB Output is correct
9 Correct 198 ms 3544 KB Output is correct
10 Correct 7 ms 512 KB Output is correct
11 Correct 111 ms 2552 KB Output is correct
12 Correct 193 ms 3704 KB Output is correct
13 Correct 200 ms 3720 KB Output is correct
14 Correct 199 ms 3512 KB Output is correct
15 Incorrect 284 ms 6108 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 7 ms 512 KB Output is correct
6 Correct 14 ms 688 KB Output is correct
7 Correct 33 ms 1152 KB Output is correct
8 Correct 82 ms 1968 KB Output is correct
9 Correct 198 ms 3544 KB Output is correct
10 Correct 7 ms 512 KB Output is correct
11 Correct 111 ms 2552 KB Output is correct
12 Correct 193 ms 3704 KB Output is correct
13 Correct 200 ms 3720 KB Output is correct
14 Correct 199 ms 3512 KB Output is correct
15 Incorrect 284 ms 6108 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 7 ms 512 KB Output is correct
6 Correct 14 ms 688 KB Output is correct
7 Correct 33 ms 1152 KB Output is correct
8 Correct 82 ms 1968 KB Output is correct
9 Correct 198 ms 3544 KB Output is correct
10 Correct 7 ms 512 KB Output is correct
11 Correct 111 ms 2552 KB Output is correct
12 Correct 193 ms 3704 KB Output is correct
13 Correct 200 ms 3720 KB Output is correct
14 Correct 199 ms 3512 KB Output is correct
15 Incorrect 284 ms 6108 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 7 ms 512 KB Output is correct
6 Correct 14 ms 688 KB Output is correct
7 Correct 33 ms 1152 KB Output is correct
8 Correct 82 ms 1968 KB Output is correct
9 Correct 198 ms 3544 KB Output is correct
10 Correct 7 ms 512 KB Output is correct
11 Correct 111 ms 2552 KB Output is correct
12 Correct 193 ms 3704 KB Output is correct
13 Correct 200 ms 3720 KB Output is correct
14 Correct 199 ms 3512 KB Output is correct
15 Incorrect 284 ms 6108 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -