Submission #830624

#	Time	Username	Problem	Language	Result	Execution time	Memory
830624		Johann	Martian DNA (BOI18_dna)	C++14	100 / 100	36 ms	4540 KiB

dna

#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<int,int>
#define vb vector<bool>
#define vi vector<int>
#define vpii vector<pii>
#define vvpii vector<vpii>
#define vvi vector<vi>
#define tiii tuple<int,int,int>
#define vtiii vector<tiii>

#define F0R(i, n) for(int i = 0; i < (n); ++i)
#define R0F(i, n) for(int i = (n)-1; i >= 0; --i)
#define sz(x) ((int)(x).size())
#define all(x) begin(x), end(x)
#define nl "\n";

int main() {
    int N, K, R;
    scanf("%d %d %d", &N, &K, &R);
    vi dna(N), cnt(K), con(K, -1);
    F0R(i,N) scanf("%d", & dna[i]);
    F0R(i,R) {
        int a,b;
        scanf("%d %d", & a, & b);
        con[a] = b;
    }
    int fullfilled = 0;
    int s = 0, t = 0;
    int ans = INT_MAX;
    while (t < N) {
        if (fullfilled == R) {
            ans = min(ans, t - s);
            --cnt[dna[s]];
            if (con[dna[s]] != -1 && cnt[dna[s]] == con[dna[s]] - 1) --fullfilled;
            ++s;
        } else {
            ++cnt[dna[t]];
            if (con[dna[t]] != -1 && cnt[dna[t]] == con[dna[t]]) ++fullfilled;
            ++t;
        }
    }
    // s aufrücken
    while (fullfilled == R) {
        ans = min(ans, t - s);
        --cnt[dna[s]];
        if (con[dna[s]] != -1 && cnt[dna[s]] == con[dna[s]] - 1) --fullfilled;
        ++s;
    }
    if (ans == INT_MAX) printf("impossible\n");
    else printf("%d\n", ans);
}

Compilation message (stderr)

dna.cpp: In function 'int main()':
dna.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     scanf("%d %d %d", &N, &K, &R);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
dna.cpp:24:19: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     F0R(i,N) scanf("%d", & dna[i]);
      |              ~~~~~^~~~~~~~~~~~~~~~
dna.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf("%d %d", & a, & b);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

• Subtask 1: 16 / 16
• Subtask 2: 24 / 24
• Subtask 3: 28 / 28
• Subtask 4: 32 / 32