oj.uz

Submission #112357

# Submission time Handle Problem Language Result Execution time Memory
112357 2019-05-19T04:08:39 Z shoemakerjo Minerals (JOI19_minerals) C++14
40 / 100
 315 ms 12396 KB 
#include "minerals.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int maxn = 100010;
ll nmask[maxn];
map<ll, int> v;

map<ll, int> ccount;
vector<int> csame[maxn];

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();
    v.clear();

    if (nc == 0) {
      for (int i = 1; i <= 2*N; i++) {
        stuff.push_back(i);
      }
      shuffle(stuff.begin(), stuff.end(), mt_rand);
    }
    else {
      for (int vv : curin) {
        // stuff.push_back(v);
        csame[vv].clear();
        if (v.count(nmask[vv])) {
          csame[v[nmask[vv]]].push_back(vv);
        }
        else {
          v[nmask[vv]] = vv;
          // csame[vv].clear();
          csame[vv].push_back(vv);
        }
      }
      for (int vv : curin) {
        if (csame[vv].size() == 0) continue;
        int omask = nmask[vv] ^ ((1 << nc) - 1);
        if (omask > nmask[vv]) continue;
        shuffle(csame[vv].begin(), csame[vv].end(), mt_rand);
        int og = v[omask];
        shuffle(csame[og].begin(), csame[og].end(), mt_rand);
        for (int i = 0; i < csame[vv].size(); i++) {
          stuff.push_back(csame[vv][i]);
          stuff.push_back(csame[og][i]);
        }
      }
    }
    // shuffle(stuff.begin(), stuff.end(), mt_rand);
    ccount.clear();
    v.clear();
    for (int vv : stuff) {
      nmask[vv] *= 2LL;
      int cur = Query(vv);
      if (cur != pres) {
        nmask[vv]++;
        pres = cur;
      }
      ccount[nmask[vv]]++;
      v[nmask[vv]] = vv;
      // cout << vv << " : " << nmask[vv] << endl;
    }
    ++nc;
    for (int vv : stuff) {
      if (ccount[nmask[vv]] > 1) continue;
      ll omask =  nmask[vv] ^ ((1LL << 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:60:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for (int i = 0; i < csame[vv].size(); i++) {
                         ~~^~~~~~~~~~~~~~~~~~
minerals.cpp:18:7: warning: unused variable 'pguy' [-Wunused-variable]
   int pguy = 0;
       ^~~~

Subtask #1
6.0 / 6.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3072 KB Output is correct
2 Correct 21 ms 3448 KB Output is correct
3 Correct 44 ms 4088 KB Output is correct
4 Correct 107 ms 5620 KB Output is correct
5 Correct 263 ms 7988 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 4 ms 2560 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 11 ms 3072 KB Output is correct
6 Correct 21 ms 3448 KB Output is correct
7 Correct 44 ms 4088 KB Output is correct
8 Correct 107 ms 5620 KB Output is correct
9 Correct 263 ms 7988 KB Output is correct
10 Correct 11 ms 2944 KB Output is correct
11 Correct 129 ms 6420 KB Output is correct
12 Correct 247 ms 8080 KB Output is correct
13 Correct 239 ms 8056 KB Output is correct
14 Correct 227 ms 8160 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 4 ms 2560 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 11 ms 3072 KB Output is correct
6 Correct 21 ms 3448 KB Output is correct
7 Correct 44 ms 4088 KB Output is correct
8 Correct 107 ms 5620 KB Output is correct
9 Correct 263 ms 7988 KB Output is correct
10 Correct 11 ms 2944 KB Output is correct
11 Correct 129 ms 6420 KB Output is correct
12 Correct 247 ms 8080 KB Output is correct
13 Correct 239 ms 8056 KB Output is correct
14 Correct 227 ms 8160 KB Output is correct
15 Incorrect 315 ms 12396 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 4 ms 2560 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 11 ms 3072 KB Output is correct
6 Correct 21 ms 3448 KB Output is correct
7 Correct 44 ms 4088 KB Output is correct
8 Correct 107 ms 5620 KB Output is correct
9 Correct 263 ms 7988 KB Output is correct
10 Correct 11 ms 2944 KB Output is correct
11 Correct 129 ms 6420 KB Output is correct
12 Correct 247 ms 8080 KB Output is correct
13 Correct 239 ms 8056 KB Output is correct
14 Correct 227 ms 8160 KB Output is correct
15 Incorrect 315 ms 12396 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 4 ms 2560 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 11 ms 3072 KB Output is correct
6 Correct 21 ms 3448 KB Output is correct
7 Correct 44 ms 4088 KB Output is correct
8 Correct 107 ms 5620 KB Output is correct
9 Correct 263 ms 7988 KB Output is correct
10 Correct 11 ms 2944 KB Output is correct
11 Correct 129 ms 6420 KB Output is correct
12 Correct 247 ms 8080 KB Output is correct
13 Correct 239 ms 8056 KB Output is correct
14 Correct 227 ms 8160 KB Output is correct
15 Incorrect 315 ms 12396 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 4 ms 2560 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 11 ms 3072 KB Output is correct
6 Correct 21 ms 3448 KB Output is correct
7 Correct 44 ms 4088 KB Output is correct
8 Correct 107 ms 5620 KB Output is correct
9 Correct 263 ms 7988 KB Output is correct
10 Correct 11 ms 2944 KB Output is correct
11 Correct 129 ms 6420 KB Output is correct
12 Correct 247 ms 8080 KB Output is correct
13 Correct 239 ms 8056 KB Output is correct
14 Correct 227 ms 8160 KB Output is correct
15 Incorrect 315 ms 12396 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 4 ms 2560 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 11 ms 3072 KB Output is correct
6 Correct 21 ms 3448 KB Output is correct
7 Correct 44 ms 4088 KB Output is correct
8 Correct 107 ms 5620 KB Output is correct
9 Correct 263 ms 7988 KB Output is correct
10 Correct 11 ms 2944 KB Output is correct
11 Correct 129 ms 6420 KB Output is correct
12 Correct 247 ms 8080 KB Output is correct
13 Correct 239 ms 8056 KB Output is correct
14 Correct 227 ms 8160 KB Output is correct
15 Incorrect 315 ms 12396 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 4 ms 2560 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 11 ms 3072 KB Output is correct
6 Correct 21 ms 3448 KB Output is correct
7 Correct 44 ms 4088 KB Output is correct
8 Correct 107 ms 5620 KB Output is correct
9 Correct 263 ms 7988 KB Output is correct
10 Correct 11 ms 2944 KB Output is correct
11 Correct 129 ms 6420 KB Output is correct
12 Correct 247 ms 8080 KB Output is correct
13 Correct 239 ms 8056 KB Output is correct
14 Correct 227 ms 8160 KB Output is correct
15 Incorrect 315 ms 12396 KB Wrong Answer [2]
16 Halted 0 ms 0 KB -