oj.uz

Submission #836175

# Submission time Handle Problem Language Result Execution time Memory
836175 2023-08-24T08:24:10 Z HollaFoil Minerals (JOI19_minerals) C++14
85 / 100
 235 ms 56692 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 1 ms 208 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 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 6 ms 2640 KB Output is correct
3 Correct 13 ms 5160 KB Output is correct
4 Correct 34 ms 10284 KB Output is correct
5 Correct 64 ms 19552 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 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 3 ms 1360 KB Output is correct
6 Correct 6 ms 2640 KB Output is correct
7 Correct 13 ms 5160 KB Output is correct
8 Correct 34 ms 10284 KB Output is correct
9 Correct 64 ms 19552 KB Output is correct
10 Correct 3 ms 1360 KB Output is correct
11 Correct 41 ms 12920 KB Output is correct
12 Correct 69 ms 19580 KB Output is correct
13 Correct 68 ms 19596 KB Output is correct
14 Correct 67 ms 19540 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 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 3 ms 1360 KB Output is correct
6 Correct 6 ms 2640 KB Output is correct
7 Correct 13 ms 5160 KB Output is correct
8 Correct 34 ms 10284 KB Output is correct
9 Correct 64 ms 19552 KB Output is correct
10 Correct 3 ms 1360 KB Output is correct
11 Correct 41 ms 12920 KB Output is correct
12 Correct 69 ms 19580 KB Output is correct
13 Correct 68 ms 19596 KB Output is correct
14 Correct 67 ms 19540 KB Output is correct
15 Correct 203 ms 51908 KB Output is correct
16 Correct 200 ms 51900 KB Output is correct
17 Correct 200 ms 51964 KB Output is correct
18 Correct 194 ms 51808 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 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 3 ms 1360 KB Output is correct
6 Correct 6 ms 2640 KB Output is correct
7 Correct 13 ms 5160 KB Output is correct
8 Correct 34 ms 10284 KB Output is correct
9 Correct 64 ms 19552 KB Output is correct
10 Correct 3 ms 1360 KB Output is correct
11 Correct 41 ms 12920 KB Output is correct
12 Correct 69 ms 19580 KB Output is correct
13 Correct 68 ms 19596 KB Output is correct
14 Correct 67 ms 19540 KB Output is correct
15 Correct 203 ms 51908 KB Output is correct
16 Correct 200 ms 51900 KB Output is correct
17 Correct 200 ms 51964 KB Output is correct
18 Correct 194 ms 51808 KB Output is correct
19 Correct 198 ms 53160 KB Output is correct
20 Correct 197 ms 53100 KB Output is correct
21 Correct 189 ms 53180 KB Output is correct
22 Correct 189 ms 53048 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 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 3 ms 1360 KB Output is correct
6 Correct 6 ms 2640 KB Output is correct
7 Correct 13 ms 5160 KB Output is correct
8 Correct 34 ms 10284 KB Output is correct
9 Correct 64 ms 19552 KB Output is correct
10 Correct 3 ms 1360 KB Output is correct
11 Correct 41 ms 12920 KB Output is correct
12 Correct 69 ms 19580 KB Output is correct
13 Correct 68 ms 19596 KB Output is correct
14 Correct 67 ms 19540 KB Output is correct
15 Correct 203 ms 51908 KB Output is correct
16 Correct 200 ms 51900 KB Output is correct
17 Correct 200 ms 51964 KB Output is correct
18 Correct 194 ms 51808 KB Output is correct
19 Correct 198 ms 53160 KB Output is correct
20 Correct 197 ms 53100 KB Output is correct
21 Correct 189 ms 53180 KB Output is correct
22 Correct 189 ms 53048 KB Output is correct
23 Correct 228 ms 54440 KB Output is correct
24 Correct 201 ms 54380 KB Output is correct
25 Correct 207 ms 54352 KB Output is correct
26 Correct 227 ms 54208 KB Output is correct

Subtask #7
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 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 3 ms 1360 KB Output is correct
6 Correct 6 ms 2640 KB Output is correct
7 Correct 13 ms 5160 KB Output is correct
8 Correct 34 ms 10284 KB Output is correct
9 Correct 64 ms 19552 KB Output is correct
10 Correct 3 ms 1360 KB Output is correct
11 Correct 41 ms 12920 KB Output is correct
12 Correct 69 ms 19580 KB Output is correct
13 Correct 68 ms 19596 KB Output is correct
14 Correct 67 ms 19540 KB Output is correct
15 Correct 203 ms 51908 KB Output is correct
16 Correct 200 ms 51900 KB Output is correct
17 Correct 200 ms 51964 KB Output is correct
18 Correct 194 ms 51808 KB Output is correct
19 Correct 198 ms 53160 KB Output is correct
20 Correct 197 ms 53100 KB Output is correct
21 Correct 189 ms 53180 KB Output is correct
22 Correct 189 ms 53048 KB Output is correct
23 Correct 228 ms 54440 KB Output is correct
24 Correct 201 ms 54380 KB Output is correct
25 Correct 207 ms 54352 KB Output is correct
26 Correct 227 ms 54208 KB Output is correct
27 Correct 217 ms 55908 KB Output is correct
28 Correct 200 ms 55972 KB Output is correct
29 Correct 217 ms 56084 KB Output is correct
30 Correct 199 ms 55820 KB Output is correct

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 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 3 ms 1360 KB Output is correct
6 Correct 6 ms 2640 KB Output is correct
7 Correct 13 ms 5160 KB Output is correct
8 Correct 34 ms 10284 KB Output is correct
9 Correct 64 ms 19552 KB Output is correct
10 Correct 3 ms 1360 KB Output is correct
11 Correct 41 ms 12920 KB Output is correct
12 Correct 69 ms 19580 KB Output is correct
13 Correct 68 ms 19596 KB Output is correct
14 Correct 67 ms 19540 KB Output is correct
15 Correct 203 ms 51908 KB Output is correct
16 Correct 200 ms 51900 KB Output is correct
17 Correct 200 ms 51964 KB Output is correct
18 Correct 194 ms 51808 KB Output is correct
19 Correct 198 ms 53160 KB Output is correct
20 Correct 197 ms 53100 KB Output is correct
21 Correct 189 ms 53180 KB Output is correct
22 Correct 189 ms 53048 KB Output is correct
23 Correct 228 ms 54440 KB Output is correct
24 Correct 201 ms 54380 KB Output is correct
25 Correct 207 ms 54352 KB Output is correct
26 Correct 227 ms 54208 KB Output is correct
27 Correct 217 ms 55908 KB Output is correct
28 Correct 200 ms 55972 KB Output is correct
29 Correct 217 ms 56084 KB Output is correct
30 Correct 199 ms 55820 KB Output is correct
31 Incorrect 235 ms 56692 KB Wrong Answer [2]
32 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 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 3 ms 1360 KB Output is correct
6 Correct 6 ms 2640 KB Output is correct
7 Correct 13 ms 5160 KB Output is correct
8 Correct 34 ms 10284 KB Output is correct
9 Correct 64 ms 19552 KB Output is correct
10 Correct 3 ms 1360 KB Output is correct
11 Correct 41 ms 12920 KB Output is correct
12 Correct 69 ms 19580 KB Output is correct
13 Correct 68 ms 19596 KB Output is correct
14 Correct 67 ms 19540 KB Output is correct
15 Correct 203 ms 51908 KB Output is correct
16 Correct 200 ms 51900 KB Output is correct
17 Correct 200 ms 51964 KB Output is correct
18 Correct 194 ms 51808 KB Output is correct
19 Correct 198 ms 53160 KB Output is correct
20 Correct 197 ms 53100 KB Output is correct
21 Correct 189 ms 53180 KB Output is correct
22 Correct 189 ms 53048 KB Output is correct
23 Correct 228 ms 54440 KB Output is correct
24 Correct 201 ms 54380 KB Output is correct
25 Correct 207 ms 54352 KB Output is correct
26 Correct 227 ms 54208 KB Output is correct
27 Correct 217 ms 55908 KB Output is correct
28 Correct 200 ms 55972 KB Output is correct
29 Correct 217 ms 56084 KB Output is correct
30 Correct 199 ms 55820 KB Output is correct
31 Incorrect 235 ms 56692 KB Wrong Answer [2]
32 Halted 0 ms 0 KB -