oj.uz

Submission #137957

# Submission time Handle Problem Language Result Execution time Memory
137957 2019-07-28T15:30:30 Z Bohoty Minerals (JOI19_minerals) C++14
90 / 100
 384 ms 17980 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.36 * 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 376 KB Output is correct
3 Correct 2 ms 252 KB Output is correct
4 Correct 2 ms 380 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 13 ms 1144 KB Output is correct
3 Correct 22 ms 1960 KB Output is correct
4 Correct 55 ms 3592 KB Output is correct
5 Correct 124 ms 6488 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 376 KB Output is correct
3 Correct 2 ms 252 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 13 ms 1144 KB Output is correct
7 Correct 22 ms 1960 KB Output is correct
8 Correct 55 ms 3592 KB Output is correct
9 Correct 124 ms 6488 KB Output is correct
10 Correct 7 ms 632 KB Output is correct
11 Correct 70 ms 4392 KB Output is correct
12 Correct 113 ms 6496 KB Output is correct
13 Correct 109 ms 6520 KB Output is correct
14 Correct 108 ms 6560 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 376 KB Output is correct
3 Correct 2 ms 252 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 13 ms 1144 KB Output is correct
7 Correct 22 ms 1960 KB Output is correct
8 Correct 55 ms 3592 KB Output is correct
9 Correct 124 ms 6488 KB Output is correct
10 Correct 7 ms 632 KB Output is correct
11 Correct 70 ms 4392 KB Output is correct
12 Correct 113 ms 6496 KB Output is correct
13 Correct 109 ms 6520 KB Output is correct
14 Correct 108 ms 6560 KB Output is correct
15 Correct 333 ms 16056 KB Output is correct
16 Correct 336 ms 16088 KB Output is correct
17 Correct 321 ms 16028 KB Output is correct
18 Correct 319 ms 16144 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 376 KB Output is correct
3 Correct 2 ms 252 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 13 ms 1144 KB Output is correct
7 Correct 22 ms 1960 KB Output is correct
8 Correct 55 ms 3592 KB Output is correct
9 Correct 124 ms 6488 KB Output is correct
10 Correct 7 ms 632 KB Output is correct
11 Correct 70 ms 4392 KB Output is correct
12 Correct 113 ms 6496 KB Output is correct
13 Correct 109 ms 6520 KB Output is correct
14 Correct 108 ms 6560 KB Output is correct
15 Correct 333 ms 16056 KB Output is correct
16 Correct 336 ms 16088 KB Output is correct
17 Correct 321 ms 16028 KB Output is correct
18 Correct 319 ms 16144 KB Output is correct
19 Correct 346 ms 16428 KB Output is correct
20 Correct 344 ms 16496 KB Output is correct
21 Correct 329 ms 16612 KB Output is correct
22 Correct 325 ms 16260 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 376 KB Output is correct
3 Correct 2 ms 252 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 13 ms 1144 KB Output is correct
7 Correct 22 ms 1960 KB Output is correct
8 Correct 55 ms 3592 KB Output is correct
9 Correct 124 ms 6488 KB Output is correct
10 Correct 7 ms 632 KB Output is correct
11 Correct 70 ms 4392 KB Output is correct
12 Correct 113 ms 6496 KB Output is correct
13 Correct 109 ms 6520 KB Output is correct
14 Correct 108 ms 6560 KB Output is correct
15 Correct 333 ms 16056 KB Output is correct
16 Correct 336 ms 16088 KB Output is correct
17 Correct 321 ms 16028 KB Output is correct
18 Correct 319 ms 16144 KB Output is correct
19 Correct 346 ms 16428 KB Output is correct
20 Correct 344 ms 16496 KB Output is correct
21 Correct 329 ms 16612 KB Output is correct
22 Correct 325 ms 16260 KB Output is correct
23 Correct 352 ms 16800 KB Output is correct
24 Correct 362 ms 16796 KB Output is correct
25 Correct 352 ms 16904 KB Output is correct
26 Correct 384 ms 16744 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 376 KB Output is correct
3 Correct 2 ms 252 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 13 ms 1144 KB Output is correct
7 Correct 22 ms 1960 KB Output is correct
8 Correct 55 ms 3592 KB Output is correct
9 Correct 124 ms 6488 KB Output is correct
10 Correct 7 ms 632 KB Output is correct
11 Correct 70 ms 4392 KB Output is correct
12 Correct 113 ms 6496 KB Output is correct
13 Correct 109 ms 6520 KB Output is correct
14 Correct 108 ms 6560 KB Output is correct
15 Correct 333 ms 16056 KB Output is correct
16 Correct 336 ms 16088 KB Output is correct
17 Correct 321 ms 16028 KB Output is correct
18 Correct 319 ms 16144 KB Output is correct
19 Correct 346 ms 16428 KB Output is correct
20 Correct 344 ms 16496 KB Output is correct
21 Correct 329 ms 16612 KB Output is correct
22 Correct 325 ms 16260 KB Output is correct
23 Correct 352 ms 16800 KB Output is correct
24 Correct 362 ms 16796 KB Output is correct
25 Correct 352 ms 16904 KB Output is correct
26 Correct 384 ms 16744 KB Output is correct
27 Correct 368 ms 17304 KB Output is correct
28 Correct 377 ms 17304 KB Output is correct
29 Correct 380 ms 17348 KB Output is correct
30 Correct 343 ms 17096 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 376 KB Output is correct
3 Correct 2 ms 252 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 13 ms 1144 KB Output is correct
7 Correct 22 ms 1960 KB Output is correct
8 Correct 55 ms 3592 KB Output is correct
9 Correct 124 ms 6488 KB Output is correct
10 Correct 7 ms 632 KB Output is correct
11 Correct 70 ms 4392 KB Output is correct
12 Correct 113 ms 6496 KB Output is correct
13 Correct 109 ms 6520 KB Output is correct
14 Correct 108 ms 6560 KB Output is correct
15 Correct 333 ms 16056 KB Output is correct
16 Correct 336 ms 16088 KB Output is correct
17 Correct 321 ms 16028 KB Output is correct
18 Correct 319 ms 16144 KB Output is correct
19 Correct 346 ms 16428 KB Output is correct
20 Correct 344 ms 16496 KB Output is correct
21 Correct 329 ms 16612 KB Output is correct
22 Correct 325 ms 16260 KB Output is correct
23 Correct 352 ms 16800 KB Output is correct
24 Correct 362 ms 16796 KB Output is correct
25 Correct 352 ms 16904 KB Output is correct
26 Correct 384 ms 16744 KB Output is correct
27 Correct 368 ms 17304 KB Output is correct
28 Correct 377 ms 17304 KB Output is correct
29 Correct 380 ms 17348 KB Output is correct
30 Correct 343 ms 17096 KB Output is correct
31 Correct 378 ms 17700 KB Output is correct
32 Correct 377 ms 17844 KB Output is correct
33 Correct 366 ms 17816 KB Output is correct
34 Correct 359 ms 17616 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 376 KB Output is correct
3 Correct 2 ms 252 KB Output is correct
4 Correct 2 ms 380 KB Output is correct
5 Correct 7 ms 760 KB Output is correct
6 Correct 13 ms 1144 KB Output is correct
7 Correct 22 ms 1960 KB Output is correct
8 Correct 55 ms 3592 KB Output is correct
9 Correct 124 ms 6488 KB Output is correct
10 Correct 7 ms 632 KB Output is correct
11 Correct 70 ms 4392 KB Output is correct
12 Correct 113 ms 6496 KB Output is correct
13 Correct 109 ms 6520 KB Output is correct
14 Correct 108 ms 6560 KB Output is correct
15 Correct 333 ms 16056 KB Output is correct
16 Correct 336 ms 16088 KB Output is correct
17 Correct 321 ms 16028 KB Output is correct
18 Correct 319 ms 16144 KB Output is correct
19 Correct 346 ms 16428 KB Output is correct
20 Correct 344 ms 16496 KB Output is correct
21 Correct 329 ms 16612 KB Output is correct
22 Correct 325 ms 16260 KB Output is correct
23 Correct 352 ms 16800 KB Output is correct
24 Correct 362 ms 16796 KB Output is correct
25 Correct 352 ms 16904 KB Output is correct
26 Correct 384 ms 16744 KB Output is correct
27 Correct 368 ms 17304 KB Output is correct
28 Correct 377 ms 17304 KB Output is correct
29 Correct 380 ms 17348 KB Output is correct
30 Correct 343 ms 17096 KB Output is correct
31 Correct 378 ms 17700 KB Output is correct
32 Correct 377 ms 17844 KB Output is correct
33 Correct 366 ms 17816 KB Output is correct
34 Correct 359 ms 17616 KB Output is correct
35 Incorrect 360 ms 17980 KB Wrong Answer [2]
36 Halted 0 ms 0 KB -