Submission #391587

#TimeUsernameProblemLanguageResultExecution timeMemory
391587Victor Martian DNA (BOI18_dna)C++17
0 / 100
71 ms5488 KiB
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i = a; i < b; ++i) #define per(i, a, b) for (int i = b - 1; i >= a; --i) #define trax(a, x) for (auto& a : x) #define sz(a) a.size() typedef pair<int, int> ii; typedef long long ll; typedef vector<int> vi; typedef vector<ii> vii; typedef vector<vi> vvi; int main() { cin.tie(0)->sync_with_stdio(0); int n, k, r, quant[200001], dna[200001]; memset(quant, 0, sizeof(quant)); cin >> n >> k >> r; rep(i, 0, n) cin >> dna[i]; rep(i, 0, r) { int b, q; cin >> b >> q; quant[b] = q; } int lo = 1, hi = n; bool imp = 1; vi curr,dummy(n); while (lo < hi) { int mid = (hi + lo) >> 1,have=0; curr=dummy; bool work=0; rep(i, 0, mid - 1){ int base=dna[i]; if(++curr[base]==quant[base])++have; } rep(i,mid-1,n){ int base=dna[i]; if(++curr[base]==quant[base])++have; if(have==r){ work=1; imp=0; break; } base=dna[i-mid+1]; if(quant[base]==curr[base]--)--have; } if(work)hi=mid; else lo=mid+1; } if(imp)cout<<"impossible"<<endl; else cout<<lo<<endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...