oj.uz

Submission #638218

# Submission time Handle Problem Language Result Execution time Memory
638218 2022-09-05T00:25:10 Z iee Grudanje (COCI19_grudanje) C++17
70 / 70
 182 ms 6164 KB 
// iee
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <set>
#include <map>

#define rep(i, a, b) for (auto i = (a); i <= (b); ++i)
#define per(i, a, b) for (auto i = (a); i >= (b); --i)
#define fi first
#define se second
using ll = long long;
using ull = unsigned long long;
using namespace std;
void work(int);

template <class T> void read(T &x) {
  x = 0; int f = 1, ch = getchar();
  while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
  while (isdigit(ch)) x = x * 10 + (ch - '0'), ch = getchar();
  x *= f;
}

int main() {
  int TT = 1; // cin >> TT;
  rep(CAS, 1, TT)
    work(CAS);
  return 0;
}
const int N = 1e5 + 5;
int n, q, p[N];
pair<int, int> qry[N];
char s[N], now[N], S[N][26];
bool ok(int mid) {
  memcpy(now, s, sizeof s);
  rep(i, 1, mid) now[p[i]] = '*';
  rep(i, 1, n) {
    rep(j, 0, 25) S[i][j] = S[i - 1][j];
    if (now[i] != '*') S[i][now[i] - 'a']++;
  }
  rep(i, 1, q) {
    rep(j, 0, 25) {
      if (S[qry[i].se][j] - S[qry[i].fi - 1][j] > 1) return 0;
    }
  }
  return 1;
}
void work(int CASE) {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  cin >> q;
  rep(i, 1, q) {
    cin >> qry[i].fi >> qry[i].se;
  }
  rep(i, 1, n) {
    cin >> p[i];
  }
  int l = 0, r = n;
  while (l < r) {
    int mid = l + r >> 1;
    if (ok(mid)) r = mid;
    else l = mid + 1;
  }
  cout << l;
}

Compilation message

grudanje.cpp: In function 'void work(int)':
grudanje.cpp:62:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |     int mid = l + r >> 1;
      |               ~~^~~
grudanje.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |   scanf("%s", s + 1);
      |   ~~~~~^~~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 440 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 468 KB Output is correct
2 Correct 6 ms 468 KB Output is correct
3 Correct 4 ms 468 KB Output is correct

Subtask #4
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 500 KB Output is correct
2 Correct 4 ms 468 KB Output is correct
3 Correct 4 ms 468 KB Output is correct

Subtask #5
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 580 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 144 ms 5992 KB Output is correct
2 Correct 114 ms 5960 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 5940 KB Output is correct
2 Correct 105 ms 5836 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 6004 KB Output is correct
2 Correct 157 ms 6040 KB Output is correct
3 Correct 122 ms 5864 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 6044 KB Output is correct
2 Correct 148 ms 6164 KB Output is correct
3 Correct 104 ms 5884 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 5928 KB Output is correct
2 Correct 144 ms 6124 KB Output is correct
3 Correct 117 ms 5928 KB Output is correct