oj.uz

Submission #137951

# Submission time Handle Problem Language Result Execution time Memory
137951 2019-07-28T15:24:26 Z Bohoty Minerals (JOI19_minerals) C++14
85 / 100
 279 ms 17400 KB 
#include "minerals.h"
//#include "grader.cpp"
#pragma GCC optimize ("O3")
#include<bits/stdc++.h>
using namespace std;
const int mxN = 2e5 + 5;
int inside[mxN], tot;
int get(int x){
  if(inside[x])
  tot--;
  else
  tot++;
  inside[x] ^= 1;
  return tot - Query(x);
}
void goKill(set<int> a, set<int> b, bool aInside, bool bInside){
  // cout << a.size() << '\n';
  if(a.size() == 2){
      int cur = get(*a.begin());
      int cur2 = get(*b.begin());
      if(aInside){
        if(cur == cur2){
          Answer(*a.begin(),*b.begin());
          Answer(*a.rbegin(),*b.rbegin());
        } else {
          Answer(*a.begin(),*b.rbegin());
          Answer(*a.rbegin(),*b.begin());
        }
      }
    else {
      if(cur != cur2){
        Answer(*a.begin(),*b.begin());
        Answer(*a.rbegin(),*b.rbegin());
      } else {
        Answer(*a.begin(),*b.rbegin());
        Answer(*a.rbegin(),*b.begin());
      }
    }
    return;
  }
  if(a.size() == 1){
    Answer(*a.begin(), *b.begin());
    return;
  }
  int sz = a.size();
  set<int> x, y;
  int b4;
  int take = ceil(0.35 * sz);
  if(aInside)take = sz - take;
  for(int j = 1; j <= ceil(0.35 * sz); j++){
    int v = *a.begin();
    a.erase(v);
    x.insert(v);
    b4 = get(v);
  }
  for(auto it : b){
    if(x.size() == y.size())continue;
    int v = get(it);
    if((!aInside && v != b4)||(aInside && v == b4)){
      y.insert(it);
    }
    b4 = v;
  }
  for(auto v : y)b.erase(v);
  goKill(x,y,aInside^1,bInside^1);
  goKill(a,b,aInside,bInside^1);
}
void Solve(int N) {
  int n = N + N;
  set<int> a, b;
  int b4 = 0;
  for (int i = 1; i <= n; i++) {
    int x = get(i);
    if(x > b4){
      a.insert(i);
    } else {
      b.insert(i);
    }
    b4 = x;
  }
  // cout << a.size() << ' ' << b.size() << '\n';
 
  goKill(a, b, 1, 1);
 
}

Compilation message

minerals.cpp: In function 'void goKill(std::set<int>, std::set<int>, bool, bool)':
minerals.cpp:59:29: warning: 'b4' may be used uninitialized in this function [-Wmaybe-uninitialized]
     if((!aInside && v != b4)||(aInside && v == b4)){
        ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 632 KB Output is correct
2 Correct 10 ms 1160 KB Output is correct
3 Correct 21 ms 1956 KB Output is correct
4 Correct 42 ms 3576 KB Output is correct
5 Correct 90 ms 6264 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 10 ms 1160 KB Output is correct
7 Correct 21 ms 1956 KB Output is correct
8 Correct 42 ms 3576 KB Output is correct
9 Correct 90 ms 6264 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 51 ms 4328 KB Output is correct
12 Correct 81 ms 6264 KB Output is correct
13 Correct 64 ms 6264 KB Output is correct
14 Correct 71 ms 6244 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 10 ms 1160 KB Output is correct
7 Correct 21 ms 1956 KB Output is correct
8 Correct 42 ms 3576 KB Output is correct
9 Correct 90 ms 6264 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 51 ms 4328 KB Output is correct
12 Correct 81 ms 6264 KB Output is correct
13 Correct 64 ms 6264 KB Output is correct
14 Correct 71 ms 6244 KB Output is correct
15 Correct 238 ms 15572 KB Output is correct
16 Correct 234 ms 15548 KB Output is correct
17 Correct 181 ms 15540 KB Output is correct
18 Correct 194 ms 15376 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 10 ms 1160 KB Output is correct
7 Correct 21 ms 1956 KB Output is correct
8 Correct 42 ms 3576 KB Output is correct
9 Correct 90 ms 6264 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 51 ms 4328 KB Output is correct
12 Correct 81 ms 6264 KB Output is correct
13 Correct 64 ms 6264 KB Output is correct
14 Correct 71 ms 6244 KB Output is correct
15 Correct 238 ms 15572 KB Output is correct
16 Correct 234 ms 15548 KB Output is correct
17 Correct 181 ms 15540 KB Output is correct
18 Correct 194 ms 15376 KB Output is correct
19 Correct 274 ms 15952 KB Output is correct
20 Correct 248 ms 16120 KB Output is correct
21 Correct 189 ms 15912 KB Output is correct
22 Correct 195 ms 16008 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 10 ms 1160 KB Output is correct
7 Correct 21 ms 1956 KB Output is correct
8 Correct 42 ms 3576 KB Output is correct
9 Correct 90 ms 6264 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 51 ms 4328 KB Output is correct
12 Correct 81 ms 6264 KB Output is correct
13 Correct 64 ms 6264 KB Output is correct
14 Correct 71 ms 6244 KB Output is correct
15 Correct 238 ms 15572 KB Output is correct
16 Correct 234 ms 15548 KB Output is correct
17 Correct 181 ms 15540 KB Output is correct
18 Correct 194 ms 15376 KB Output is correct
19 Correct 274 ms 15952 KB Output is correct
20 Correct 248 ms 16120 KB Output is correct
21 Correct 189 ms 15912 KB Output is correct
22 Correct 195 ms 16008 KB Output is correct
23 Correct 252 ms 16376 KB Output is correct
24 Correct 250 ms 16384 KB Output is correct
25 Correct 202 ms 16492 KB Output is correct
26 Correct 200 ms 16120 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 10 ms 1160 KB Output is correct
7 Correct 21 ms 1956 KB Output is correct
8 Correct 42 ms 3576 KB Output is correct
9 Correct 90 ms 6264 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 51 ms 4328 KB Output is correct
12 Correct 81 ms 6264 KB Output is correct
13 Correct 64 ms 6264 KB Output is correct
14 Correct 71 ms 6244 KB Output is correct
15 Correct 238 ms 15572 KB Output is correct
16 Correct 234 ms 15548 KB Output is correct
17 Correct 181 ms 15540 KB Output is correct
18 Correct 194 ms 15376 KB Output is correct
19 Correct 274 ms 15952 KB Output is correct
20 Correct 248 ms 16120 KB Output is correct
21 Correct 189 ms 15912 KB Output is correct
22 Correct 195 ms 16008 KB Output is correct
23 Correct 252 ms 16376 KB Output is correct
24 Correct 250 ms 16384 KB Output is correct
25 Correct 202 ms 16492 KB Output is correct
26 Correct 200 ms 16120 KB Output is correct
27 Correct 271 ms 16680 KB Output is correct
28 Correct 279 ms 16812 KB Output is correct
29 Correct 198 ms 16760 KB Output is correct
30 Correct 206 ms 16624 KB Output is correct

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 10 ms 1160 KB Output is correct
7 Correct 21 ms 1956 KB Output is correct
8 Correct 42 ms 3576 KB Output is correct
9 Correct 90 ms 6264 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 51 ms 4328 KB Output is correct
12 Correct 81 ms 6264 KB Output is correct
13 Correct 64 ms 6264 KB Output is correct
14 Correct 71 ms 6244 KB Output is correct
15 Correct 238 ms 15572 KB Output is correct
16 Correct 234 ms 15548 KB Output is correct
17 Correct 181 ms 15540 KB Output is correct
18 Correct 194 ms 15376 KB Output is correct
19 Correct 274 ms 15952 KB Output is correct
20 Correct 248 ms 16120 KB Output is correct
21 Correct 189 ms 15912 KB Output is correct
22 Correct 195 ms 16008 KB Output is correct
23 Correct 252 ms 16376 KB Output is correct
24 Correct 250 ms 16384 KB Output is correct
25 Correct 202 ms 16492 KB Output is correct
26 Correct 200 ms 16120 KB Output is correct
27 Correct 271 ms 16680 KB Output is correct
28 Correct 279 ms 16812 KB Output is correct
29 Correct 198 ms 16760 KB Output is correct
30 Correct 206 ms 16624 KB Output is correct
31 Correct 260 ms 17256 KB Output is correct
32 Correct 268 ms 17400 KB Output is correct
33 Correct 207 ms 17172 KB Output is correct
34 Incorrect 194 ms 17104 KB Wrong Answer [2]

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 10 ms 1160 KB Output is correct
7 Correct 21 ms 1956 KB Output is correct
8 Correct 42 ms 3576 KB Output is correct
9 Correct 90 ms 6264 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 51 ms 4328 KB Output is correct
12 Correct 81 ms 6264 KB Output is correct
13 Correct 64 ms 6264 KB Output is correct
14 Correct 71 ms 6244 KB Output is correct
15 Correct 238 ms 15572 KB Output is correct
16 Correct 234 ms 15548 KB Output is correct
17 Correct 181 ms 15540 KB Output is correct
18 Correct 194 ms 15376 KB Output is correct
19 Correct 274 ms 15952 KB Output is correct
20 Correct 248 ms 16120 KB Output is correct
21 Correct 189 ms 15912 KB Output is correct
22 Correct 195 ms 16008 KB Output is correct
23 Correct 252 ms 16376 KB Output is correct
24 Correct 250 ms 16384 KB Output is correct
25 Correct 202 ms 16492 KB Output is correct
26 Correct 200 ms 16120 KB Output is correct
27 Correct 271 ms 16680 KB Output is correct
28 Correct 279 ms 16812 KB Output is correct
29 Correct 198 ms 16760 KB Output is correct
30 Correct 206 ms 16624 KB Output is correct
31 Correct 260 ms 17256 KB Output is correct
32 Correct 268 ms 17400 KB Output is correct
33 Correct 207 ms 17172 KB Output is correct
34 Incorrect 194 ms 17104 KB Wrong Answer [2]