Submission #399756

#TimeUsernameProblemLanguageResultExecution timeMemory
399756Sorting Martian DNA (BOI18_dna)C++17
100 / 100
39 ms2720 KiB
#include <bits/stdc++.h> using namespace std; template<typename T> void check_min(T &a, const T &b){ a = (a < b) ? a : b; } template<typename T> void check_max(T &a, const T &b){ a = (a > b) ? a : b; } typedef long long ll; #define all(x) (x).begin(), (x).end() int read_int(); const int N = 2e5 + 3; int n, k, r, a[N]; int mn[N], cnt[N], cnt_ok; void add(int x){ ++cnt[x]; if(cnt[x] == mn[x]) ++cnt_ok; } void rem(int x){ if(cnt[x] == mn[x]) --cnt_ok; --cnt[x]; } bool check(int mid){ fill(cnt, cnt + k, 0); cnt_ok = k - r; for(int i = 0; i < mid; ++i) add(a[i]); if(cnt_ok == k) return true; for(int i = mid; i < n; ++i){ add(a[i]); rem(a[i - mid]); if(cnt_ok == k) return true; } return false; } int main(){ ios::sync_with_stdio(false); cin.tie(NULL); n = read_int(), k = read_int(), r = read_int(); for(int i = 0; i < n; ++i) a[i] = read_int(); for(int i = 0; i < r; ++i){ int b, q; b = read_int(), q = read_int(); mn[b] = q; } int l = 1, r = n + 1; while(l != r){ int mid = (l + r) >> 1; if(check(mid)) r = mid; else l = mid + 1; } if(l == n + 1) cout << "impossible\n"; else cout << l << "\n"; } int ptr = N - 1; char buff[N]; void next_char(){ if(++ptr == N) fread(buff, 1, N, stdin), ptr = 0; } int read_int(){ int ret = 0; for(; buff[ptr] < '0' || buff[ptr] > '9'; next_char()); for(; '0' <= buff[ptr] && buff[ptr] <= '9'; next_char()) ret = 10 * ret + buff[ptr] - '0'; return ret; }

Compilation message (stderr)

dna.cpp: In function 'void next_char()':
dna.cpp:68:39: warning: ignoring return value of 'size_t fread(void*, size_t, size_t, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   68 | void next_char(){ if(++ptr == N) fread(buff, 1, N, stdin), ptr = 0; }
      |                                  ~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...