oj.uz

Submission #537988

# Submission time Handle Problem Language Result Execution time Memory
537988 2022-03-16T02:05:38 Z thegrimbee Martian DNA (BOI18_dna) C++14
0 / 100
 59 ms 5456 KB 
	#include<bits/stdc++.h>
	using namespace std;
	#define int long long
	bool debug = false;
	signed main(){
		cin.tie(0);
		ios_base::sync_with_stdio(0);
		int n, k, r, temp; cin >> n >> k >> r;
		bool found = false;
		vector<int> v(n);
		for (int i = 0 ;i < n; ++i){
			cin >> v[i];
		}
		vector<int> val(k, 1e9+7);
		for (int i = 0;i < r; ++i){
			cin >> temp;
			cin >> val[temp];
		}
		int lo = 1, hi = n+1, mid = (lo + hi)/2;
		temp = 0;
		while (lo < hi-1){
			if(debug) cout << lo << ' ' << mid << ' ' << hi << "    ";
			temp = 0;
			found = false;
			vector<int> cur(n, 0);
			for (int i = 0; i < mid; ++i){
				cur[v[i]]++;
				if(cur[v[i]] == val[v[i]])temp++;
			}
			if(debug)cout << temp << ' ';
			if(temp == r){
				hi = mid;
				mid = (lo + hi)/2;
				if(debug)cout <<'\n';
				continue;
			}
			for (int i = mid; i < n && !found; ++i){
				cur[v[i]]++;
				cur[v[i-mid]]--;
				if (v[i] != v[i-mid]){
					if(cur[v[i]] == val[v[i]])temp++;
					if (cur[v[i-mid]] == val[v[i-mid]]-1)temp--;
				}
				if(debug)cout << temp << ' ' ;
				if(temp == r){
					hi = mid;
					mid = (lo + hi)/2;
					if(debug)cout<<'\n';
					found = true;
					continue;
				}
			}
			if(found)continue;
			if(debug)cout<<'\n';
			lo = mid;
			mid = (lo + hi)/2;
		}
		if(debug)cout << temp << ' ';
		if (temp != r && mid == n+1)cout << "impossible";
		else cout << hi;

	}

Subtask #1
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Incorrect 1 ms 212 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 324 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 368 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 316 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Incorrect 0 ms 212 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 3432 KB Output is correct
2 Correct 37 ms 3412 KB Output is correct
3 Correct 23 ms 3896 KB Output is correct
4 Correct 31 ms 3796 KB Output is correct
5 Correct 42 ms 5240 KB Output is correct
6 Correct 25 ms 3784 KB Output is correct
7 Incorrect 25 ms 4016 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 5336 KB Output is correct
2 Correct 47 ms 5456 KB Output is correct
3 Correct 59 ms 5208 KB Output is correct
4 Incorrect 13 ms 3792 KB Output isn't correct
5 Halted 0 ms 0 KB -