oj.uz

Submission #855979

# Submission time Handle Problem Language Result Execution time Memory
855979 2023-10-02T13:21:14 Z RiverFlow Martian DNA (BOI18_dna) C++14
68 / 100
 101 ms 148308 KB 
#include <bits/stdc++.h>

#define nl "\n"
#define no "NO"
#define yes "YES"
#define fi first
#define se second
#define vec vector
#define task "main"
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
#define unq(x) sort(all(x)); x.resize(unique(all(x)) - x.begin())

using namespace std;

template<typename U, typename V> bool maxi(U &a, V b) {
    if (a < b) { a = b; return 1; } return 0;
}
template<typename U, typename V> bool mini(U &a, V b) {
    if (a > b) { a = b; return 1; } return 0;
}

const int N = (int)2e5 + 9;
const int mod = (int)1e9 + 7;

void prepare(); void main_code();

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")) {
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    const bool MULTITEST = 0; prepare();
    int num_test = 1; if (MULTITEST) cin >> num_test;
    while (num_test--) { main_code(); }
}

void prepare() {};

int a[N], cnt[12][N], b[N], q[N], ind[N];

int n, k, r;

bool check(int x, int y) {
    FOR(i, 1, r)
        if (cnt[i][y] - cnt[i][x - 1] < q[i]) return 0;
    return 1;
}

void subtask3() {
    FOR(j, 1, r) {
        FOR(i, 1, n) cnt[j][i] = cnt[j][i - 1] + (a[i] == j);
    }
    int res = n + 1, j = 1;
    FOR(i, 1, n) {
        while (j <= i and check(j, i)) {
            res = min(res, i - j + 1); ++j;
        }
    }
    if (res == n + 1)
        evoid("impossible");
    cout << res;
}

int c[N];

queue<int> pos[N];

bool ok[N];

void main_code() {
    cin >> n >> k >> r;
    FOR(i, 1, n) cin >> a[i], ++a[i];

    FOR(i, 1, r) cin >> b[i] >> q[i], ++b[i];

    FOR(i, 1, r) ind[b[i]] = i; ind[0] = 0;

    FOR(i, 1, n) a[i] = ind[ a[i] ];

    if (r <= 10) return subtask3(), void();

    int j = 1, d = 0, ans = n + 1;

    FOR(i, 1, n) {
        int v = a[i]; if (v == 0) continue ;
        pos[v].push(i);
        d -= ok[j];
        ok[j] |= sz(pos[v]) == q[v];
        d += ok[j];
        while (sz(pos[v]) > q[v] and pos[v].front() == j) {
            pos[v].pop(); ++j;
            while (j <= i and a[j] == 0) ++j;
        }

        if (d == r) {
            ans = min(ans, i - j + 1);
        }
    }

    if (ans == n + 1)
        evoid("impossible");

    cout << ans;
}


/*     Let the river flows naturally     */

Compilation message

dna.cpp: In function 'void main_code()':
dna.cpp:15:22: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   15 | #define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
      |                      ^~~
dna.cpp:83:5: note: in expansion of macro 'FOR'
   83 |     FOR(i, 1, r) ind[b[i]] = i; ind[0] = 0;
      |     ^~~
dna.cpp:83:33: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   83 |     FOR(i, 1, r) ind[b[i]] = i; ind[0] = 0;
      |                                 ^~~
dna.cpp: In function 'int main()':
dna.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dna.cpp:37:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 139856 KB Output is correct
2 Correct 71 ms 139856 KB Output is correct
3 Correct 67 ms 139860 KB Output is correct
4 Correct 71 ms 139856 KB Output is correct
5 Correct 78 ms 140112 KB Output is correct
6 Correct 68 ms 139812 KB Output is correct
7 Correct 71 ms 139856 KB Output is correct
8 Correct 69 ms 139856 KB Output is correct
9 Correct 71 ms 139856 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 140116 KB Output is correct
2 Correct 69 ms 140116 KB Output is correct
3 Correct 68 ms 140112 KB Output is correct
4 Correct 70 ms 140144 KB Output is correct
5 Correct 70 ms 140312 KB Output is correct
6 Correct 68 ms 140172 KB Output is correct
7 Correct 67 ms 139788 KB Output is correct
8 Correct 71 ms 140208 KB Output is correct
9 Correct 67 ms 139856 KB Output is correct
10 Correct 70 ms 139860 KB Output is correct
11 Correct 76 ms 139984 KB Output is correct
12 Correct 70 ms 139916 KB Output is correct
13 Correct 69 ms 139860 KB Output is correct
14 Correct 69 ms 139860 KB Output is correct
15 Correct 68 ms 139856 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 147540 KB Output is correct
2 Correct 81 ms 141124 KB Output is correct
3 Correct 89 ms 147540 KB Output is correct
4 Correct 101 ms 147536 KB Output is correct
5 Correct 89 ms 148300 KB Output is correct
6 Correct 85 ms 147828 KB Output is correct
7 Correct 86 ms 147744 KB Output is correct
8 Correct 89 ms 148308 KB Output is correct
9 Correct 94 ms 148244 KB Output is correct
10 Correct 83 ms 147632 KB Output is correct
11 Correct 77 ms 139980 KB Output is correct
12 Correct 70 ms 140140 KB Output is correct
13 Correct 69 ms 140116 KB Output is correct
14 Correct 69 ms 140120 KB Output is correct
15 Correct 72 ms 140348 KB Output is correct
16 Correct 69 ms 140112 KB Output is correct
17 Correct 67 ms 139848 KB Output is correct
18 Correct 70 ms 139988 KB Output is correct
19 Correct 68 ms 139860 KB Output is correct
20 Correct 70 ms 139860 KB Output is correct
21 Correct 67 ms 139956 KB Output is correct
22 Correct 85 ms 139860 KB Output is correct
23 Correct 68 ms 139860 KB Output is correct
24 Correct 69 ms 139856 KB Output is correct
25 Correct 68 ms 139860 KB Output is correct

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Incorrect 99 ms 141944 KB Output isn't correct
2 Halted 0 ms 0 KB -