oj.uz

Submission #874378

# Submission time Handle Problem Language Result Execution time Memory
874378 2023-11-16T19:46:16 Z mgl_diamond JJOOII 2 (JOI20_ho_t2) C++17
100 / 100
 7 ms 1688 KB 
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
 
#define foru(i, l, r) for(int i=(l); i<=(r); ++i)
#define ford(i, l, r) for(int i=(l); i>=(r); --i)
#define fore(x, v) for(auto &x : v)
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
#define fi first
#define se second
#define file "input"

template<class T> bool minimize(T &a, T b) { if (a > b) { a = b; return 1; } return 0; }
template<class T> bool maximize(T &a, T b) { if (a < b) { a = b; return 1; } return 0; }

void setIO() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  if (fopen(file".inp", "r")) {
    freopen(file".inp", "r", stdin);
    freopen(file".out", "w", stdout);
  }
}

const int N = 1e5+5;
int n, k;
vector<int> pos[3];

int main() {
  setIO();

  cin >> n >> k;
  foru(i, 0, n-1) {
    char ch;
    cin >> ch;
    if (ch == 'J') pos[0].push_back(i);
    else if (ch == 'O') pos[1].push_back(i);
    else pos[2].push_back(i);
  }

  if (sz(pos[0]) < k || sz(pos[1]) < k || sz(pos[1]) < k) {
    cout << -1;
    return 0;
  }

  int x = -1, y = 0, z = sz(pos[2]), ans = n+1;
  while (z-1 >= 0 && pos[2][z-1] > pos[1][k-1])
    --z;
  
  foru(y, 0, sz(pos[1])-k) {
    while (x+1 < sz(pos[0]) && pos[0][x+1] < pos[1][y])
      ++x;
    
    while (z < sz(pos[2]) && pos[2][z] < pos[1][y+k-1])
      ++z;
    
    if (x-k+1 >= 0 && z+k-1 < sz(pos[2])) {
      int ff = (pos[0][x] - pos[0][x-k+1] + 1 - k);
      int ss = (pos[1][y+k-1] - pos[1][y] + 1 - k);
      int th = (pos[2][z+k-1] - pos[2][z] + 1 - k);
      minimize(ans, ff + ss + th + pos[1][y] - pos[0][x] - 1 + pos[2][z] - pos[1][y+k-1] - 1);
    }
  }

  cout << (ans == n+1 ? -1 : ans);
}

Compilation message

ho_t2.cpp: In function 'int main()':
ho_t2.cpp:48:15: warning: unused variable 'y' [-Wunused-variable]
   48 |   int x = -1, y = 0, z = sz(pos[2]), ans = n+1;
      |               ^
ho_t2.cpp: In function 'void setIO()':
ho_t2.cpp:22:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     freopen(file".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
ho_t2.cpp:23:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     freopen(file".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 596 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct

Subtask #3
87.0 / 87.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 596 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 1 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 1 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 5 ms 1240 KB Output is correct
37 Correct 6 ms 1432 KB Output is correct
38 Correct 6 ms 1484 KB Output is correct
39 Correct 6 ms 1492 KB Output is correct
40 Correct 7 ms 1500 KB Output is correct
41 Correct 6 ms 1500 KB Output is correct
42 Correct 6 ms 1500 KB Output is correct
43 Correct 4 ms 1120 KB Output is correct
44 Correct 4 ms 1244 KB Output is correct
45 Correct 6 ms 1632 KB Output is correct
46 Correct 6 ms 1500 KB Output is correct
47 Correct 6 ms 1496 KB Output is correct
48 Correct 6 ms 1628 KB Output is correct
49 Correct 4 ms 1240 KB Output is correct
50 Correct 6 ms 1500 KB Output is correct
51 Correct 6 ms 1500 KB Output is correct
52 Correct 4 ms 1240 KB Output is correct
53 Correct 5 ms 1632 KB Output is correct
54 Correct 3 ms 1688 KB Output is correct
55 Correct 3 ms 1632 KB Output is correct
56 Correct 3 ms 1632 KB Output is correct