oj.uz

Submission #137939

# Submission time Handle Problem Language Result Execution time Memory
137939 2019-07-28T14:52:31 Z Bohoty Minerals (JOI19_minerals) C++14
80 / 100
 268 ms 13480 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){
  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 <= sz / 2; 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:55: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 380 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 252 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 9 ms 888 KB Output is correct
3 Correct 19 ms 1656 KB Output is correct
4 Correct 41 ms 2808 KB Output is correct
5 Correct 82 ms 4984 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 380 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 9 ms 888 KB Output is correct
7 Correct 19 ms 1656 KB Output is correct
8 Correct 41 ms 2808 KB Output is correct
9 Correct 82 ms 4984 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 52 ms 3496 KB Output is correct
12 Correct 82 ms 5112 KB Output is correct
13 Correct 65 ms 5112 KB Output is correct
14 Correct 69 ms 5056 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 380 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 9 ms 888 KB Output is correct
7 Correct 19 ms 1656 KB Output is correct
8 Correct 41 ms 2808 KB Output is correct
9 Correct 82 ms 4984 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 52 ms 3496 KB Output is correct
12 Correct 82 ms 5112 KB Output is correct
13 Correct 65 ms 5112 KB Output is correct
14 Correct 69 ms 5056 KB Output is correct
15 Correct 248 ms 12480 KB Output is correct
16 Correct 242 ms 12500 KB Output is correct
17 Correct 191 ms 12568 KB Output is correct
18 Correct 191 ms 12388 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 380 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 9 ms 888 KB Output is correct
7 Correct 19 ms 1656 KB Output is correct
8 Correct 41 ms 2808 KB Output is correct
9 Correct 82 ms 4984 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 52 ms 3496 KB Output is correct
12 Correct 82 ms 5112 KB Output is correct
13 Correct 65 ms 5112 KB Output is correct
14 Correct 69 ms 5056 KB Output is correct
15 Correct 248 ms 12480 KB Output is correct
16 Correct 242 ms 12500 KB Output is correct
17 Correct 191 ms 12568 KB Output is correct
18 Correct 191 ms 12388 KB Output is correct
19 Correct 268 ms 12924 KB Output is correct
20 Correct 264 ms 12960 KB Output is correct
21 Correct 194 ms 12792 KB Output is correct
22 Correct 196 ms 12684 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 380 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 9 ms 888 KB Output is correct
7 Correct 19 ms 1656 KB Output is correct
8 Correct 41 ms 2808 KB Output is correct
9 Correct 82 ms 4984 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 52 ms 3496 KB Output is correct
12 Correct 82 ms 5112 KB Output is correct
13 Correct 65 ms 5112 KB Output is correct
14 Correct 69 ms 5056 KB Output is correct
15 Correct 248 ms 12480 KB Output is correct
16 Correct 242 ms 12500 KB Output is correct
17 Correct 191 ms 12568 KB Output is correct
18 Correct 191 ms 12388 KB Output is correct
19 Correct 268 ms 12924 KB Output is correct
20 Correct 264 ms 12960 KB Output is correct
21 Correct 194 ms 12792 KB Output is correct
22 Correct 196 ms 12684 KB Output is correct
23 Correct 268 ms 13176 KB Output is correct
24 Correct 267 ms 13232 KB Output is correct
25 Correct 222 ms 13096 KB Output is correct
26 Correct 214 ms 12920 KB Output is correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 9 ms 888 KB Output is correct
7 Correct 19 ms 1656 KB Output is correct
8 Correct 41 ms 2808 KB Output is correct
9 Correct 82 ms 4984 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 52 ms 3496 KB Output is correct
12 Correct 82 ms 5112 KB Output is correct
13 Correct 65 ms 5112 KB Output is correct
14 Correct 69 ms 5056 KB Output is correct
15 Correct 248 ms 12480 KB Output is correct
16 Correct 242 ms 12500 KB Output is correct
17 Correct 191 ms 12568 KB Output is correct
18 Correct 191 ms 12388 KB Output is correct
19 Correct 268 ms 12924 KB Output is correct
20 Correct 264 ms 12960 KB Output is correct
21 Correct 194 ms 12792 KB Output is correct
22 Correct 196 ms 12684 KB Output is correct
23 Correct 268 ms 13176 KB Output is correct
24 Correct 267 ms 13232 KB Output is correct
25 Correct 222 ms 13096 KB Output is correct
26 Correct 214 ms 12920 KB Output is correct
27 Incorrect 267 ms 13480 KB Wrong Answer [2]
28 Halted 0 ms 0 KB -

Subtask #8
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 9 ms 888 KB Output is correct
7 Correct 19 ms 1656 KB Output is correct
8 Correct 41 ms 2808 KB Output is correct
9 Correct 82 ms 4984 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 52 ms 3496 KB Output is correct
12 Correct 82 ms 5112 KB Output is correct
13 Correct 65 ms 5112 KB Output is correct
14 Correct 69 ms 5056 KB Output is correct
15 Correct 248 ms 12480 KB Output is correct
16 Correct 242 ms 12500 KB Output is correct
17 Correct 191 ms 12568 KB Output is correct
18 Correct 191 ms 12388 KB Output is correct
19 Correct 268 ms 12924 KB Output is correct
20 Correct 264 ms 12960 KB Output is correct
21 Correct 194 ms 12792 KB Output is correct
22 Correct 196 ms 12684 KB Output is correct
23 Correct 268 ms 13176 KB Output is correct
24 Correct 267 ms 13232 KB Output is correct
25 Correct 222 ms 13096 KB Output is correct
26 Correct 214 ms 12920 KB Output is correct
27 Incorrect 267 ms 13480 KB Wrong Answer [2]
28 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 380 KB Output is correct
3 Correct 2 ms 248 KB Output is correct
4 Correct 2 ms 252 KB Output is correct
5 Correct 5 ms 632 KB Output is correct
6 Correct 9 ms 888 KB Output is correct
7 Correct 19 ms 1656 KB Output is correct
8 Correct 41 ms 2808 KB Output is correct
9 Correct 82 ms 4984 KB Output is correct
10 Correct 5 ms 632 KB Output is correct
11 Correct 52 ms 3496 KB Output is correct
12 Correct 82 ms 5112 KB Output is correct
13 Correct 65 ms 5112 KB Output is correct
14 Correct 69 ms 5056 KB Output is correct
15 Correct 248 ms 12480 KB Output is correct
16 Correct 242 ms 12500 KB Output is correct
17 Correct 191 ms 12568 KB Output is correct
18 Correct 191 ms 12388 KB Output is correct
19 Correct 268 ms 12924 KB Output is correct
20 Correct 264 ms 12960 KB Output is correct
21 Correct 194 ms 12792 KB Output is correct
22 Correct 196 ms 12684 KB Output is correct
23 Correct 268 ms 13176 KB Output is correct
24 Correct 267 ms 13232 KB Output is correct
25 Correct 222 ms 13096 KB Output is correct
26 Correct 214 ms 12920 KB Output is correct
27 Incorrect 267 ms 13480 KB Wrong Answer [2]
28 Halted 0 ms 0 KB -