oj.uz

Submission #836171

# Submission time Handle Problem Language Result Execution time Memory
836171 2023-08-24T08:21:22 Z HollaFoil Minerals (JOI19_minerals) C++14
85 / 100
 173 ms 53296 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>, unordered_set<int>> candidates;

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

void InitRand(int N) {
  srand(5);
  vector<int> order(2*N);
  for (int i = 0; i < 2*N; i++) order[i]=i;
  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) {
  //cout << "Preparing intervals: " << "in - (" << inserted.first << "; " << inserted.second << ")  target - (" << interval.first << "; " << interval.second << ")\n";
  for (int i = min(inserted.first, interval.first); i <= max(inserted.second, interval.second); i++) {
    bool a = false;
    bool b = false;
    if (i >= inserted.first && i <= inserted.second) a = true;
    if (i >= interval.first && i <= interval.second) b = true;
    if (a != b) q = Q(lefts[i]);
  }
}

void search(int i, int j) {
  //cout << "Searching i=" << i << " j=" << j << endl;
  if (i == j) return;
  int a = i;
  int b = (i + j) / 2;
  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);
  inserted = l;
  int lcount = b - a + 1;
  int rcount = j - i + 1;
  //cout << "L = (" << a << "; " << b << ")        R = (" << i << "; " << j << ")\n";
  for (auto candidate : candidates[full]) {
    int c = candidate;
    //cout << "  Candidate " << c << " - ";

    if (lcount == 0) {
      candidates[r].insert(c);
      rcount--;
      continue;
    }
    else if (rcount == 0) {
      candidates[l].insert(c);
      lcount--;
      continue;
    }
    //cout << " (passed sanity) ";
    int next = Q(c);
    if (q == next) {
      candidates[l].insert(c);
      lcount--;
      //cout << " left" << endl;
    }
    else {
      candidates[r].insert(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].insert(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].insert(i);
    }
    else {
      q = next;
      lefts.push_back(i);
    }
  }
  inserted = make_pair(0, N-1);
  //cout << "Left: ";
  for (auto i : lefts) {
    //cout << i << " ";
  }
  //cout << endl << "Candidates: ";
  for (auto c : candidates[interval]) {
    //cout << c << " ";
  }
  //cout << endl;

  search(0, N-1);
  for (int i = 0; i < N; i++) {
    int a = m[lefts[i]];
    int b = m[*(candidates[make_pair(i, i)].begin())];
    //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:108:13: warning: unused variable 'i' [-Wunused-variable]
  108 |   for (auto i : lefts) {
      |             ^
minerals.cpp:112:13: warning: unused variable 'c' [-Wunused-variable]
  112 |   for (auto c : candidates[interval]) {
      |             ^

Subtask #1
6.0 / 6.0

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

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1360 KB Output is correct
2 Correct 5 ms 2384 KB Output is correct
3 Correct 11 ms 4816 KB Output is correct
4 Correct 25 ms 9656 KB Output is correct
5 Correct 54 ms 18356 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 3 ms 1360 KB Output is correct
6 Correct 5 ms 2384 KB Output is correct
7 Correct 11 ms 4816 KB Output is correct
8 Correct 25 ms 9656 KB Output is correct
9 Correct 54 ms 18356 KB Output is correct
10 Correct 3 ms 1360 KB Output is correct
11 Correct 33 ms 12160 KB Output is correct
12 Correct 55 ms 18364 KB Output is correct
13 Correct 45 ms 18468 KB Output is correct
14 Correct 46 ms 18484 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 3 ms 1360 KB Output is correct
6 Correct 5 ms 2384 KB Output is correct
7 Correct 11 ms 4816 KB Output is correct
8 Correct 25 ms 9656 KB Output is correct
9 Correct 54 ms 18356 KB Output is correct
10 Correct 3 ms 1360 KB Output is correct
11 Correct 33 ms 12160 KB Output is correct
12 Correct 55 ms 18364 KB Output is correct
13 Correct 45 ms 18468 KB Output is correct
14 Correct 46 ms 18484 KB Output is correct
15 Correct 158 ms 48932 KB Output is correct
16 Correct 162 ms 48880 KB Output is correct
17 Correct 125 ms 48940 KB Output is correct
18 Correct 120 ms 48680 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 3 ms 1360 KB Output is correct
6 Correct 5 ms 2384 KB Output is correct
7 Correct 11 ms 4816 KB Output is correct
8 Correct 25 ms 9656 KB Output is correct
9 Correct 54 ms 18356 KB Output is correct
10 Correct 3 ms 1360 KB Output is correct
11 Correct 33 ms 12160 KB Output is correct
12 Correct 55 ms 18364 KB Output is correct
13 Correct 45 ms 18468 KB Output is correct
14 Correct 46 ms 18484 KB Output is correct
15 Correct 158 ms 48932 KB Output is correct
16 Correct 162 ms 48880 KB Output is correct
17 Correct 125 ms 48940 KB Output is correct
18 Correct 120 ms 48680 KB Output is correct
19 Correct 162 ms 50064 KB Output is correct
20 Correct 167 ms 50000 KB Output is correct
21 Correct 131 ms 49984 KB Output is correct
22 Correct 124 ms 49836 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 3 ms 1360 KB Output is correct
6 Correct 5 ms 2384 KB Output is correct
7 Correct 11 ms 4816 KB Output is correct
8 Correct 25 ms 9656 KB Output is correct
9 Correct 54 ms 18356 KB Output is correct
10 Correct 3 ms 1360 KB Output is correct
11 Correct 33 ms 12160 KB Output is correct
12 Correct 55 ms 18364 KB Output is correct
13 Correct 45 ms 18468 KB Output is correct
14 Correct 46 ms 18484 KB Output is correct
15 Correct 158 ms 48932 KB Output is correct
16 Correct 162 ms 48880 KB Output is correct
17 Correct 125 ms 48940 KB Output is correct
18 Correct 120 ms 48680 KB Output is correct
19 Correct 162 ms 50064 KB Output is correct
20 Correct 167 ms 50000 KB Output is correct
21 Correct 131 ms 49984 KB Output is correct
22 Correct 124 ms 49836 KB Output is correct
23 Correct 166 ms 51252 KB Output is correct
24 Correct 172 ms 51152 KB Output is correct
25 Correct 135 ms 51264 KB Output is correct
26 Correct 133 ms 51088 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 3 ms 1360 KB Output is correct
6 Correct 5 ms 2384 KB Output is correct
7 Correct 11 ms 4816 KB Output is correct
8 Correct 25 ms 9656 KB Output is correct
9 Correct 54 ms 18356 KB Output is correct
10 Correct 3 ms 1360 KB Output is correct
11 Correct 33 ms 12160 KB Output is correct
12 Correct 55 ms 18364 KB Output is correct
13 Correct 45 ms 18468 KB Output is correct
14 Correct 46 ms 18484 KB Output is correct
15 Correct 158 ms 48932 KB Output is correct
16 Correct 162 ms 48880 KB Output is correct
17 Correct 125 ms 48940 KB Output is correct
18 Correct 120 ms 48680 KB Output is correct
19 Correct 162 ms 50064 KB Output is correct
20 Correct 167 ms 50000 KB Output is correct
21 Correct 131 ms 49984 KB Output is correct
22 Correct 124 ms 49836 KB Output is correct
23 Correct 166 ms 51252 KB Output is correct
24 Correct 172 ms 51152 KB Output is correct
25 Correct 135 ms 51264 KB Output is correct
26 Correct 133 ms 51088 KB Output is correct
27 Correct 172 ms 52728 KB Output is correct
28 Correct 173 ms 52640 KB Output is correct
29 Correct 135 ms 52736 KB Output is correct
30 Correct 133 ms 52480 KB Output is correct

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 3 ms 1360 KB Output is correct
6 Correct 5 ms 2384 KB Output is correct
7 Correct 11 ms 4816 KB Output is correct
8 Correct 25 ms 9656 KB Output is correct
9 Correct 54 ms 18356 KB Output is correct
10 Correct 3 ms 1360 KB Output is correct
11 Correct 33 ms 12160 KB Output is correct
12 Correct 55 ms 18364 KB Output is correct
13 Correct 45 ms 18468 KB Output is correct
14 Correct 46 ms 18484 KB Output is correct
15 Correct 158 ms 48932 KB Output is correct
16 Correct 162 ms 48880 KB Output is correct
17 Correct 125 ms 48940 KB Output is correct
18 Correct 120 ms 48680 KB Output is correct
19 Correct 162 ms 50064 KB Output is correct
20 Correct 167 ms 50000 KB Output is correct
21 Correct 131 ms 49984 KB Output is correct
22 Correct 124 ms 49836 KB Output is correct
23 Correct 166 ms 51252 KB Output is correct
24 Correct 172 ms 51152 KB Output is correct
25 Correct 135 ms 51264 KB Output is correct
26 Correct 133 ms 51088 KB Output is correct
27 Correct 172 ms 52728 KB Output is correct
28 Correct 173 ms 52640 KB Output is correct
29 Correct 135 ms 52736 KB Output is correct
30 Correct 133 ms 52480 KB Output is correct
31 Incorrect 173 ms 53296 KB Wrong Answer [2]
32 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 3 ms 1360 KB Output is correct
6 Correct 5 ms 2384 KB Output is correct
7 Correct 11 ms 4816 KB Output is correct
8 Correct 25 ms 9656 KB Output is correct
9 Correct 54 ms 18356 KB Output is correct
10 Correct 3 ms 1360 KB Output is correct
11 Correct 33 ms 12160 KB Output is correct
12 Correct 55 ms 18364 KB Output is correct
13 Correct 45 ms 18468 KB Output is correct
14 Correct 46 ms 18484 KB Output is correct
15 Correct 158 ms 48932 KB Output is correct
16 Correct 162 ms 48880 KB Output is correct
17 Correct 125 ms 48940 KB Output is correct
18 Correct 120 ms 48680 KB Output is correct
19 Correct 162 ms 50064 KB Output is correct
20 Correct 167 ms 50000 KB Output is correct
21 Correct 131 ms 49984 KB Output is correct
22 Correct 124 ms 49836 KB Output is correct
23 Correct 166 ms 51252 KB Output is correct
24 Correct 172 ms 51152 KB Output is correct
25 Correct 135 ms 51264 KB Output is correct
26 Correct 133 ms 51088 KB Output is correct
27 Correct 172 ms 52728 KB Output is correct
28 Correct 173 ms 52640 KB Output is correct
29 Correct 135 ms 52736 KB Output is correct
30 Correct 133 ms 52480 KB Output is correct
31 Incorrect 173 ms 53296 KB Wrong Answer [2]
32 Halted 0 ms 0 KB -