Submission #1111276

#TimeUsernameProblemLanguageResultExecution timeMemory
1111276huyngodzz Martian DNA (BOI18_dna)C++14
68 / 100
66 ms14472 KiB
///huynhocute123/// #include<bits/stdc++.h> using namespace std; #define S second #define F first #define pii pair<int,int> #define piii pair<int,pair<int,int>> #define pb push_back #define FOR(i, a, b) for(int i = a; i <= b; ++i) #define REP(i, a, b) for(int i = b; i >= a; --i) #define ALL(v) v.begin(),v.end() #define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin); #define out(name) if(fopen(name, "w")) freopen(name, "w", stdout); //random_device rd; //mt19937 rng(rd()); //#pragma GCC optimize ("O3") //#pragma GCC optimize ("unroll-loops") //#pragma GCC target("popcnt") //#define int long long const int maxN = 2 * 1e5 + 9 ; const int modd = 1e9 + 7; const int base = 2309; const int MAX = 1e9+9; const double pi = 3.14159265358979323846; const double rad = 3.14159265358979323846 /180; void minimize(int &u, int v){ if(v < u) u = v; } void maximize(int &u, int v){ if(v > u) u = v; } int n, k, t, m, res, a[maxN], ori[maxN],f[15][maxN]; int l, r; pii q[maxN]; bool vis[maxN]; vector<int> e[maxN]; void compress(){ vector<int > tmp; FOR(i, 1, k)tmp.pb(q[i].F); sort(ALL(tmp)); FOR(i, 1, k){ ori[i] = q[i].F; q[i].F = lower_bound(ALL(tmp), q[i].F) -tmp.begin() +1; } } bool check(int st, int en){ FOR(i, 1, k){ if(f[q[i].F][en] - f[q[i].F][st-1] < q[i].S)return 0; } return 1; } pii get(int st){ FOR(i, 1, k){ if(f[q[i].F][n] - f[q[i].F][st-1] < q[i].S)return {0, 0}; } l = st; r = n; while(l <= r){ int mid = (l +r)/2; if(check(st, mid))r =mid -1; else l =mid + 1; } return {1, l}; } void solve(){ cin >> n >> k >> k; FOR(i, 1, n)cin >> a[i]; FOR(i, 1, k)cin >>q[i].F >> q[i].S; compress(); FOR(i, 1, n){ FOR(j, 1, k){ f[q[j].F][i]+= f[q[j].F ][i-1]; } FOR(j, 1, k){ if(ori[j] == a[i]){ f[q[j].F][i]++; break; } } } res = MAX; FOR(i, 1, n){ pii ans = get(i); if(ans.F == 0)break; minimize(res, ans.S - i +1); // cout << i << " " << ans.S << '\n'; } if(res == MAX)cout << "impossible"; else cout << res; // cout << q[2].F; // cout << f[q[1].F][n]; } signed main(){ // freopen("name.inp","r",stdin); // freopen("name.out","w",stdout); ios_base::sync_with_stdio(false); cin.tie(0); inp("task.inp"); int tc = 1; // cin >> tc; while( tc-- )solve(); cerr << '\n' << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << " s\n" ; }

Compilation message (stderr)

dna.cpp: In function 'int main()':
dna.cpp:12:47: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | #define inp(name) if(fopen(name, "r")) freopen(name, "r", stdin);
      |                                        ~~~~~~~^~~~~~~~~~~~~~~~~~
dna.cpp:103:5: note: in expansion of macro 'inp'
  103 |     inp("task.inp");
      |     ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...