oj.uz

Submission #137946

# Submission time Handle Problem Language Result Execution time Memory
137946 2019-07-28T15:12:09 Z Bohoty Minerals (JOI19_minerals) C++14
85 / 100
 259 ms 17088 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;
  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){
    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:56: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 376 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 248 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 760 KB Output is correct
2 Correct 10 ms 1144 KB Output is correct
3 Correct 19 ms 1784 KB Output is correct
4 Correct 41 ms 3448 KB Output is correct
5 Correct 80 ms 6228 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 760 KB Output is correct
6 Correct 10 ms 1144 KB Output is correct
7 Correct 19 ms 1784 KB Output is correct
8 Correct 41 ms 3448 KB Output is correct
9 Correct 80 ms 6228 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 50 ms 4216 KB Output is correct
12 Correct 79 ms 6396 KB Output is correct
13 Correct 66 ms 6228 KB Output is correct
14 Correct 67 ms 6392 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 760 KB Output is correct
6 Correct 10 ms 1144 KB Output is correct
7 Correct 19 ms 1784 KB Output is correct
8 Correct 41 ms 3448 KB Output is correct
9 Correct 80 ms 6228 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 50 ms 4216 KB Output is correct
12 Correct 79 ms 6396 KB Output is correct
13 Correct 66 ms 6228 KB Output is correct
14 Correct 67 ms 6392 KB Output is correct
15 Correct 243 ms 15684 KB Output is correct
16 Correct 235 ms 15476 KB Output is correct
17 Correct 187 ms 15608 KB Output is correct
18 Correct 190 ms 15424 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 760 KB Output is correct
6 Correct 10 ms 1144 KB Output is correct
7 Correct 19 ms 1784 KB Output is correct
8 Correct 41 ms 3448 KB Output is correct
9 Correct 80 ms 6228 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 50 ms 4216 KB Output is correct
12 Correct 79 ms 6396 KB Output is correct
13 Correct 66 ms 6228 KB Output is correct
14 Correct 67 ms 6392 KB Output is correct
15 Correct 243 ms 15684 KB Output is correct
16 Correct 235 ms 15476 KB Output is correct
17 Correct 187 ms 15608 KB Output is correct
18 Correct 190 ms 15424 KB Output is correct
19 Correct 238 ms 15976 KB Output is correct
20 Correct 242 ms 15992 KB Output is correct
21 Correct 191 ms 15880 KB Output is correct
22 Correct 192 ms 15736 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 760 KB Output is correct
6 Correct 10 ms 1144 KB Output is correct
7 Correct 19 ms 1784 KB Output is correct
8 Correct 41 ms 3448 KB Output is correct
9 Correct 80 ms 6228 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 50 ms 4216 KB Output is correct
12 Correct 79 ms 6396 KB Output is correct
13 Correct 66 ms 6228 KB Output is correct
14 Correct 67 ms 6392 KB Output is correct
15 Correct 243 ms 15684 KB Output is correct
16 Correct 235 ms 15476 KB Output is correct
17 Correct 187 ms 15608 KB Output is correct
18 Correct 190 ms 15424 KB Output is correct
19 Correct 238 ms 15976 KB Output is correct
20 Correct 242 ms 15992 KB Output is correct
21 Correct 191 ms 15880 KB Output is correct
22 Correct 192 ms 15736 KB Output is correct
23 Correct 257 ms 16376 KB Output is correct
24 Correct 256 ms 16364 KB Output is correct
25 Correct 199 ms 16376 KB Output is correct
26 Correct 209 ms 16164 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 760 KB Output is correct
6 Correct 10 ms 1144 KB Output is correct
7 Correct 19 ms 1784 KB Output is correct
8 Correct 41 ms 3448 KB Output is correct
9 Correct 80 ms 6228 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 50 ms 4216 KB Output is correct
12 Correct 79 ms 6396 KB Output is correct
13 Correct 66 ms 6228 KB Output is correct
14 Correct 67 ms 6392 KB Output is correct
15 Correct 243 ms 15684 KB Output is correct
16 Correct 235 ms 15476 KB Output is correct
17 Correct 187 ms 15608 KB Output is correct
18 Correct 190 ms 15424 KB Output is correct
19 Correct 238 ms 15976 KB Output is correct
20 Correct 242 ms 15992 KB Output is correct
21 Correct 191 ms 15880 KB Output is correct
22 Correct 192 ms 15736 KB Output is correct
23 Correct 257 ms 16376 KB Output is correct
24 Correct 256 ms 16364 KB Output is correct
25 Correct 199 ms 16376 KB Output is correct
26 Correct 209 ms 16164 KB Output is correct
27 Correct 256 ms 16784 KB Output is correct
28 Correct 259 ms 16760 KB Output is correct
29 Correct 206 ms 16760 KB Output is correct
30 Correct 209 ms 16620 KB Output is correct

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 760 KB Output is correct
6 Correct 10 ms 1144 KB Output is correct
7 Correct 19 ms 1784 KB Output is correct
8 Correct 41 ms 3448 KB Output is correct
9 Correct 80 ms 6228 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 50 ms 4216 KB Output is correct
12 Correct 79 ms 6396 KB Output is correct
13 Correct 66 ms 6228 KB Output is correct
14 Correct 67 ms 6392 KB Output is correct
15 Correct 243 ms 15684 KB Output is correct
16 Correct 235 ms 15476 KB Output is correct
17 Correct 187 ms 15608 KB Output is correct
18 Correct 190 ms 15424 KB Output is correct
19 Correct 238 ms 15976 KB Output is correct
20 Correct 242 ms 15992 KB Output is correct
21 Correct 191 ms 15880 KB Output is correct
22 Correct 192 ms 15736 KB Output is correct
23 Correct 257 ms 16376 KB Output is correct
24 Correct 256 ms 16364 KB Output is correct
25 Correct 199 ms 16376 KB Output is correct
26 Correct 209 ms 16164 KB Output is correct
27 Correct 256 ms 16784 KB Output is correct
28 Correct 259 ms 16760 KB Output is correct
29 Correct 206 ms 16760 KB Output is correct
30 Correct 209 ms 16620 KB Output is correct
31 Incorrect 253 ms 17088 KB Wrong Answer [2]
32 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 248 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 248 KB Output is correct
5 Correct 5 ms 760 KB Output is correct
6 Correct 10 ms 1144 KB Output is correct
7 Correct 19 ms 1784 KB Output is correct
8 Correct 41 ms 3448 KB Output is correct
9 Correct 80 ms 6228 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 50 ms 4216 KB Output is correct
12 Correct 79 ms 6396 KB Output is correct
13 Correct 66 ms 6228 KB Output is correct
14 Correct 67 ms 6392 KB Output is correct
15 Correct 243 ms 15684 KB Output is correct
16 Correct 235 ms 15476 KB Output is correct
17 Correct 187 ms 15608 KB Output is correct
18 Correct 190 ms 15424 KB Output is correct
19 Correct 238 ms 15976 KB Output is correct
20 Correct 242 ms 15992 KB Output is correct
21 Correct 191 ms 15880 KB Output is correct
22 Correct 192 ms 15736 KB Output is correct
23 Correct 257 ms 16376 KB Output is correct
24 Correct 256 ms 16364 KB Output is correct
25 Correct 199 ms 16376 KB Output is correct
26 Correct 209 ms 16164 KB Output is correct
27 Correct 256 ms 16784 KB Output is correct
28 Correct 259 ms 16760 KB Output is correct
29 Correct 206 ms 16760 KB Output is correct
30 Correct 209 ms 16620 KB Output is correct
31 Incorrect 253 ms 17088 KB Wrong Answer [2]
32 Halted 0 ms 0 KB -