oj.uz

Submission #836209

# Submission time Handle Problem Language Result Execution time Memory
836209 2023-08-24T08:50:34 Z HollaFoil Minerals (JOI19_minerals) C++14
80 / 100
 201 ms 67660 KB 
#include "minerals.h"
#include <bits/stdc++.h>
using namespace std;

unordered_map<int, int> m;
unordered_map<int, int> unm;
map<pair<int,int>, queue<int>> candidates;

int Q(int i) {
  return Query(m[i]+1);
}

void InitRand(int N) {
  srand(7);
  vector<int> order(2*N);
  for (int i = 0; i < 2*N; i++) order[i]=i;
  random_shuffle(order.begin(), order.end());
  random_shuffle(order.begin(), order.end());
  for (int i = 0; i < 2*N; i++) {
    m[i]=order[i];
    unm[order[i]]=i;
    //m[i] = i;
  }
}

pair<int,int> inserted;
vector<int> lefts;
int q = -1;

void prepareInterval(pair<int,int> interval, pair<int, int> full) {
  //cout << "Preparing intervals: " << "in - (" << inserted.first << "; " << inserted.second << ")  target - (" << interval.first << "; " << interval.second << ")\n";
  for (int i = full.first; i <= full.second; i++) {
    bool a = false;
    bool b = false;
    bool c = false;
    if (i >= inserted.first && i <= inserted.second) a = true;
    if (i >= interval.first && i <= interval.second) b = true;
    if (i >= full.first && i <= full.second) c = true;
    if (a != b && c) q = Q(lefts[i]);
  }
}

void search(int i, int j) {
  //cout << "Searching i=" << i << " j=" << j << endl;
  if (i == j) return;
  int diff = j - i + 1;
  int a = i;
  int b = a + (diff*10)/27;
  i = b + 1;
  pair<int, int> full = make_pair(a, j);
  pair<int, int> l = make_pair(a, b);
  pair<int, int> r = make_pair(i, j);
  prepareInterval(l, full);
  inserted = l;
  int lcount = b - a + 1;
  int rcount = j - i + 1;
  //cout << "L = (" << a << "; " << b << ")        R = (" << i << "; " << j << ")\n";
  while (!candidates[full].empty()) {
    int c = candidates[full].front();
    candidates[full].pop();
    //cout << "  Candidate " << c << " - ";

    if (lcount == 0) {
      candidates[r].push(c);
      rcount--;
      continue;
    }
    else if (rcount == 0) {
      candidates[l].push(c);
      lcount--;
      continue;
    }
    //cout << " (passed sanity) ";
    int next = Q(c);
    if (q == next) {
      candidates[l].push(c);
      lcount--;
      //cout << " left" << endl;
    }
    else {
      candidates[r].push(c);
      rcount--;
      //cout << " right" << endl;
    }
    q = next;
  }

  search(a, b);
  search(i, j);
}

void Solve(int N) {
  InitRand(N);
  pair<int,int> interval = make_pair(0, 2*N-1);
  for (int i = 0; i < 2*N; i++) {
    candidates[interval].push(i);
  }
  interval = make_pair(0, N-1);
  q = Q(0);
  lefts.push_back(0);
  for (int i = 1; i < 2*N; i++) {
    int next = Q(i);
    if (q == next) {
      candidates[interval].push(i);
    }
    else {
      q = next;
      lefts.push_back(i);
    }
  }
  inserted = make_pair(0, N-1);
  //cout << "Left: ";
  for (auto i : lefts) {
    //cout << i << " ";
  }

  search(0, N-1);
  for (int i = 0; i < N; i++) {
    int a = m[lefts[i]];
    int b = m[candidates[make_pair(i, i)].front()];
    //cout << a << " = " << b << endl;
    Answer(a+1, b+1);
  }


}
/*

4
0 4
1 5
2 3
6 7

*/

Compilation message

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:113:13: warning: unused variable 'i' [-Wunused-variable]
  113 |   for (auto i : lefts) {
      |             ^

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 0 ms 464 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1888 KB Output is correct
2 Correct 5 ms 3536 KB Output is correct
3 Correct 12 ms 6904 KB Output is correct
4 Correct 27 ms 13488 KB Output is correct
5 Correct 59 ms 24976 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 0 ms 464 KB Output is correct
5 Correct 3 ms 1888 KB Output is correct
6 Correct 5 ms 3536 KB Output is correct
7 Correct 12 ms 6904 KB Output is correct
8 Correct 27 ms 13488 KB Output is correct
9 Correct 59 ms 24976 KB Output is correct
10 Correct 3 ms 1872 KB Output is correct
11 Correct 33 ms 16612 KB Output is correct
12 Correct 57 ms 25104 KB Output is correct
13 Correct 60 ms 25048 KB Output is correct
14 Correct 61 ms 25036 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 0 ms 464 KB Output is correct
5 Correct 3 ms 1888 KB Output is correct
6 Correct 5 ms 3536 KB Output is correct
7 Correct 12 ms 6904 KB Output is correct
8 Correct 27 ms 13488 KB Output is correct
9 Correct 59 ms 24976 KB Output is correct
10 Correct 3 ms 1872 KB Output is correct
11 Correct 33 ms 16612 KB Output is correct
12 Correct 57 ms 25104 KB Output is correct
13 Correct 60 ms 25048 KB Output is correct
14 Correct 61 ms 25036 KB Output is correct
15 Correct 181 ms 62832 KB Output is correct
16 Correct 176 ms 62712 KB Output is correct
17 Correct 188 ms 62724 KB Output is correct
18 Correct 176 ms 62660 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 0 ms 464 KB Output is correct
5 Correct 3 ms 1888 KB Output is correct
6 Correct 5 ms 3536 KB Output is correct
7 Correct 12 ms 6904 KB Output is correct
8 Correct 27 ms 13488 KB Output is correct
9 Correct 59 ms 24976 KB Output is correct
10 Correct 3 ms 1872 KB Output is correct
11 Correct 33 ms 16612 KB Output is correct
12 Correct 57 ms 25104 KB Output is correct
13 Correct 60 ms 25048 KB Output is correct
14 Correct 61 ms 25036 KB Output is correct
15 Correct 181 ms 62832 KB Output is correct
16 Correct 176 ms 62712 KB Output is correct
17 Correct 188 ms 62724 KB Output is correct
18 Correct 176 ms 62660 KB Output is correct
19 Correct 179 ms 64428 KB Output is correct
20 Correct 182 ms 64428 KB Output is correct
21 Correct 184 ms 64464 KB Output is correct
22 Correct 182 ms 64220 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 0 ms 464 KB Output is correct
5 Correct 3 ms 1888 KB Output is correct
6 Correct 5 ms 3536 KB Output is correct
7 Correct 12 ms 6904 KB Output is correct
8 Correct 27 ms 13488 KB Output is correct
9 Correct 59 ms 24976 KB Output is correct
10 Correct 3 ms 1872 KB Output is correct
11 Correct 33 ms 16612 KB Output is correct
12 Correct 57 ms 25104 KB Output is correct
13 Correct 60 ms 25048 KB Output is correct
14 Correct 61 ms 25036 KB Output is correct
15 Correct 181 ms 62832 KB Output is correct
16 Correct 176 ms 62712 KB Output is correct
17 Correct 188 ms 62724 KB Output is correct
18 Correct 176 ms 62660 KB Output is correct
19 Correct 179 ms 64428 KB Output is correct
20 Correct 182 ms 64428 KB Output is correct
21 Correct 184 ms 64464 KB Output is correct
22 Correct 182 ms 64220 KB Output is correct
23 Correct 191 ms 66052 KB Output is correct
24 Correct 190 ms 66044 KB Output is correct
25 Correct 191 ms 66044 KB Output is correct
26 Correct 182 ms 65840 KB Output is correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 0 ms 464 KB Output is correct
5 Correct 3 ms 1888 KB Output is correct
6 Correct 5 ms 3536 KB Output is correct
7 Correct 12 ms 6904 KB Output is correct
8 Correct 27 ms 13488 KB Output is correct
9 Correct 59 ms 24976 KB Output is correct
10 Correct 3 ms 1872 KB Output is correct
11 Correct 33 ms 16612 KB Output is correct
12 Correct 57 ms 25104 KB Output is correct
13 Correct 60 ms 25048 KB Output is correct
14 Correct 61 ms 25036 KB Output is correct
15 Correct 181 ms 62832 KB Output is correct
16 Correct 176 ms 62712 KB Output is correct
17 Correct 188 ms 62724 KB Output is correct
18 Correct 176 ms 62660 KB Output is correct
19 Correct 179 ms 64428 KB Output is correct
20 Correct 182 ms 64428 KB Output is correct
21 Correct 184 ms 64464 KB Output is correct
22 Correct 182 ms 64220 KB Output is correct
23 Correct 191 ms 66052 KB Output is correct
24 Correct 190 ms 66044 KB Output is correct
25 Correct 191 ms 66044 KB Output is correct
26 Correct 182 ms 65840 KB Output is correct
27 Correct 201 ms 67584 KB Output is correct
28 Correct 187 ms 67660 KB Output is correct
29 Correct 193 ms 67620 KB Output is correct
30 Incorrect 176 ms 67252 KB Wrong Answer [2]
31 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 0 ms 464 KB Output is correct
5 Correct 3 ms 1888 KB Output is correct
6 Correct 5 ms 3536 KB Output is correct
7 Correct 12 ms 6904 KB Output is correct
8 Correct 27 ms 13488 KB Output is correct
9 Correct 59 ms 24976 KB Output is correct
10 Correct 3 ms 1872 KB Output is correct
11 Correct 33 ms 16612 KB Output is correct
12 Correct 57 ms 25104 KB Output is correct
13 Correct 60 ms 25048 KB Output is correct
14 Correct 61 ms 25036 KB Output is correct
15 Correct 181 ms 62832 KB Output is correct
16 Correct 176 ms 62712 KB Output is correct
17 Correct 188 ms 62724 KB Output is correct
18 Correct 176 ms 62660 KB Output is correct
19 Correct 179 ms 64428 KB Output is correct
20 Correct 182 ms 64428 KB Output is correct
21 Correct 184 ms 64464 KB Output is correct
22 Correct 182 ms 64220 KB Output is correct
23 Correct 191 ms 66052 KB Output is correct
24 Correct 190 ms 66044 KB Output is correct
25 Correct 191 ms 66044 KB Output is correct
26 Correct 182 ms 65840 KB Output is correct
27 Correct 201 ms 67584 KB Output is correct
28 Correct 187 ms 67660 KB Output is correct
29 Correct 193 ms 67620 KB Output is correct
30 Incorrect 176 ms 67252 KB Wrong Answer [2]
31 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 464 KB Output is correct
4 Correct 0 ms 464 KB Output is correct
5 Correct 3 ms 1888 KB Output is correct
6 Correct 5 ms 3536 KB Output is correct
7 Correct 12 ms 6904 KB Output is correct
8 Correct 27 ms 13488 KB Output is correct
9 Correct 59 ms 24976 KB Output is correct
10 Correct 3 ms 1872 KB Output is correct
11 Correct 33 ms 16612 KB Output is correct
12 Correct 57 ms 25104 KB Output is correct
13 Correct 60 ms 25048 KB Output is correct
14 Correct 61 ms 25036 KB Output is correct
15 Correct 181 ms 62832 KB Output is correct
16 Correct 176 ms 62712 KB Output is correct
17 Correct 188 ms 62724 KB Output is correct
18 Correct 176 ms 62660 KB Output is correct
19 Correct 179 ms 64428 KB Output is correct
20 Correct 182 ms 64428 KB Output is correct
21 Correct 184 ms 64464 KB Output is correct
22 Correct 182 ms 64220 KB Output is correct
23 Correct 191 ms 66052 KB Output is correct
24 Correct 190 ms 66044 KB Output is correct
25 Correct 191 ms 66044 KB Output is correct
26 Correct 182 ms 65840 KB Output is correct
27 Correct 201 ms 67584 KB Output is correct
28 Correct 187 ms 67660 KB Output is correct
29 Correct 193 ms 67620 KB Output is correct
30 Incorrect 176 ms 67252 KB Wrong Answer [2]
31 Halted 0 ms 0 KB -