oj.uz

Submission #137956

# Submission time Handle Problem Language Result Execution time Memory
137956 2019-07-28T15:30:10 Z Bohoty Minerals (JOI19_minerals) C++14
90 / 100
 480 ms 17968 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;
  }
  std::vector<int> o;
  for(auto x : b)o.push_back(x);
  random_shuffle(o.begin(),o.end());
  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);
  }
  b.clear();
  for(auto it : o){
    if(x.size() == y.size())b.insert(it);
    else {
    int v = get(it);
    if((!aInside && v != b4)||(aInside && v == b4)){
      y.insert(it);
    } else b.insert(it);
    b4 = v;
    }
  }
  goKill(x,y,aInside^1,bInside^1);
  goKill(a,b,aInside,bInside^1);
}
void Solve(int N) {
  srand(time(0));
  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:64: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 376 KB Output is correct

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 760 KB Output is correct
2 Correct 12 ms 1144 KB Output is correct
3 Correct 25 ms 1912 KB Output is correct
4 Correct 52 ms 3588 KB Output is correct
5 Correct 112 ms 6516 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 376 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 12 ms 1144 KB Output is correct
7 Correct 25 ms 1912 KB Output is correct
8 Correct 52 ms 3588 KB Output is correct
9 Correct 112 ms 6516 KB Output is correct
10 Correct 6 ms 760 KB Output is correct
11 Correct 69 ms 4392 KB Output is correct
12 Correct 110 ms 6596 KB Output is correct
13 Correct 107 ms 6652 KB Output is correct
14 Correct 108 ms 6496 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 376 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 12 ms 1144 KB Output is correct
7 Correct 25 ms 1912 KB Output is correct
8 Correct 52 ms 3588 KB Output is correct
9 Correct 112 ms 6516 KB Output is correct
10 Correct 6 ms 760 KB Output is correct
11 Correct 69 ms 4392 KB Output is correct
12 Correct 110 ms 6596 KB Output is correct
13 Correct 107 ms 6652 KB Output is correct
14 Correct 108 ms 6496 KB Output is correct
15 Correct 329 ms 16136 KB Output is correct
16 Correct 480 ms 16256 KB Output is correct
17 Correct 323 ms 16136 KB Output is correct
18 Correct 316 ms 15952 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 376 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 12 ms 1144 KB Output is correct
7 Correct 25 ms 1912 KB Output is correct
8 Correct 52 ms 3588 KB Output is correct
9 Correct 112 ms 6516 KB Output is correct
10 Correct 6 ms 760 KB Output is correct
11 Correct 69 ms 4392 KB Output is correct
12 Correct 110 ms 6596 KB Output is correct
13 Correct 107 ms 6652 KB Output is correct
14 Correct 108 ms 6496 KB Output is correct
15 Correct 329 ms 16136 KB Output is correct
16 Correct 480 ms 16256 KB Output is correct
17 Correct 323 ms 16136 KB Output is correct
18 Correct 316 ms 15952 KB Output is correct
19 Correct 352 ms 16520 KB Output is correct
20 Correct 341 ms 16392 KB Output is correct
21 Correct 331 ms 16484 KB Output is correct
22 Correct 326 ms 16304 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 376 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 12 ms 1144 KB Output is correct
7 Correct 25 ms 1912 KB Output is correct
8 Correct 52 ms 3588 KB Output is correct
9 Correct 112 ms 6516 KB Output is correct
10 Correct 6 ms 760 KB Output is correct
11 Correct 69 ms 4392 KB Output is correct
12 Correct 110 ms 6596 KB Output is correct
13 Correct 107 ms 6652 KB Output is correct
14 Correct 108 ms 6496 KB Output is correct
15 Correct 329 ms 16136 KB Output is correct
16 Correct 480 ms 16256 KB Output is correct
17 Correct 323 ms 16136 KB Output is correct
18 Correct 316 ms 15952 KB Output is correct
19 Correct 352 ms 16520 KB Output is correct
20 Correct 341 ms 16392 KB Output is correct
21 Correct 331 ms 16484 KB Output is correct
22 Correct 326 ms 16304 KB Output is correct
23 Correct 353 ms 16912 KB Output is correct
24 Correct 359 ms 17020 KB Output is correct
25 Correct 343 ms 16924 KB Output is correct
26 Correct 342 ms 16804 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 376 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 12 ms 1144 KB Output is correct
7 Correct 25 ms 1912 KB Output is correct
8 Correct 52 ms 3588 KB Output is correct
9 Correct 112 ms 6516 KB Output is correct
10 Correct 6 ms 760 KB Output is correct
11 Correct 69 ms 4392 KB Output is correct
12 Correct 110 ms 6596 KB Output is correct
13 Correct 107 ms 6652 KB Output is correct
14 Correct 108 ms 6496 KB Output is correct
15 Correct 329 ms 16136 KB Output is correct
16 Correct 480 ms 16256 KB Output is correct
17 Correct 323 ms 16136 KB Output is correct
18 Correct 316 ms 15952 KB Output is correct
19 Correct 352 ms 16520 KB Output is correct
20 Correct 341 ms 16392 KB Output is correct
21 Correct 331 ms 16484 KB Output is correct
22 Correct 326 ms 16304 KB Output is correct
23 Correct 353 ms 16912 KB Output is correct
24 Correct 359 ms 17020 KB Output is correct
25 Correct 343 ms 16924 KB Output is correct
26 Correct 342 ms 16804 KB Output is correct
27 Correct 387 ms 17352 KB Output is correct
28 Correct 413 ms 17432 KB Output is correct
29 Correct 346 ms 17296 KB Output is correct
30 Correct 345 ms 17304 KB Output is correct

Subtask #8
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 376 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 12 ms 1144 KB Output is correct
7 Correct 25 ms 1912 KB Output is correct
8 Correct 52 ms 3588 KB Output is correct
9 Correct 112 ms 6516 KB Output is correct
10 Correct 6 ms 760 KB Output is correct
11 Correct 69 ms 4392 KB Output is correct
12 Correct 110 ms 6596 KB Output is correct
13 Correct 107 ms 6652 KB Output is correct
14 Correct 108 ms 6496 KB Output is correct
15 Correct 329 ms 16136 KB Output is correct
16 Correct 480 ms 16256 KB Output is correct
17 Correct 323 ms 16136 KB Output is correct
18 Correct 316 ms 15952 KB Output is correct
19 Correct 352 ms 16520 KB Output is correct
20 Correct 341 ms 16392 KB Output is correct
21 Correct 331 ms 16484 KB Output is correct
22 Correct 326 ms 16304 KB Output is correct
23 Correct 353 ms 16912 KB Output is correct
24 Correct 359 ms 17020 KB Output is correct
25 Correct 343 ms 16924 KB Output is correct
26 Correct 342 ms 16804 KB Output is correct
27 Correct 387 ms 17352 KB Output is correct
28 Correct 413 ms 17432 KB Output is correct
29 Correct 346 ms 17296 KB Output is correct
30 Correct 345 ms 17304 KB Output is correct
31 Correct 373 ms 17672 KB Output is correct
32 Correct 377 ms 17848 KB Output is correct
33 Correct 360 ms 17672 KB Output is correct
34 Correct 356 ms 17464 KB Output is correct

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 376 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 12 ms 1144 KB Output is correct
7 Correct 25 ms 1912 KB Output is correct
8 Correct 52 ms 3588 KB Output is correct
9 Correct 112 ms 6516 KB Output is correct
10 Correct 6 ms 760 KB Output is correct
11 Correct 69 ms 4392 KB Output is correct
12 Correct 110 ms 6596 KB Output is correct
13 Correct 107 ms 6652 KB Output is correct
14 Correct 108 ms 6496 KB Output is correct
15 Correct 329 ms 16136 KB Output is correct
16 Correct 480 ms 16256 KB Output is correct
17 Correct 323 ms 16136 KB Output is correct
18 Correct 316 ms 15952 KB Output is correct
19 Correct 352 ms 16520 KB Output is correct
20 Correct 341 ms 16392 KB Output is correct
21 Correct 331 ms 16484 KB Output is correct
22 Correct 326 ms 16304 KB Output is correct
23 Correct 353 ms 16912 KB Output is correct
24 Correct 359 ms 17020 KB Output is correct
25 Correct 343 ms 16924 KB Output is correct
26 Correct 342 ms 16804 KB Output is correct
27 Correct 387 ms 17352 KB Output is correct
28 Correct 413 ms 17432 KB Output is correct
29 Correct 346 ms 17296 KB Output is correct
30 Correct 345 ms 17304 KB Output is correct
31 Correct 373 ms 17672 KB Output is correct
32 Correct 377 ms 17848 KB Output is correct
33 Correct 360 ms 17672 KB Output is correct
34 Correct 356 ms 17464 KB Output is correct
35 Incorrect 355 ms 17968 KB Wrong Answer [2]
36 Halted 0 ms 0 KB -