답안 #330265

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
330265	2020-11-24T10:30:05 Z	nandonathaniel	Martian DNA (BOI18_dna)	C++14	68 / 100	2000 ms	13036 KB

dna

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

int mini[200005],byk[200005];
int s[200005];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
    int n,k,r,x,y;
    cin >> n >> k >> r;
    for(int i=1;i<=n;i++)cin >> s[i];
    for(int i=1;i<=r;i++){
    	cin >> x >> y;
    	mini[x]=y;
	}
	int ki=1,ka=n,ans=n+1;
	while(ki<=ka){
		int mid=(ki+ka)/2;
		set<int> valid;
		for(int i=0;i<k;i++){
			if(mini[i]==0)valid.insert(i);
			byk[i]=0;
		}
		for(int i=1;i<=mid;i++){
			byk[s[i]]++;
			if(byk[s[i]]==mini[s[i]])valid.insert(s[i]);
		}
		if(valid.size()==k){
			ans=mid;
			ka=mid-1;
			continue;
		}
		bool ada=false;
		for(int i=mid+1;i<=n;i++){
			byk[s[i-mid]]--;
			if(byk[s[i-mid]]==mini[s[i-mid]]-1)valid.erase(s[i-mid]);
			byk[s[i]]++;
			if(byk[s[i]]==mini[s[i]])valid.insert(s[i]);
			if(valid.size()==k){
				ada=true;
				break;
			}
		}
		if(ada){
			ans=mid;
			ka=mid-1;
		}
		else ki=mid+1;
	}
	if(ans==n+1)cout << "impossible\n";
	else cout << ans << '\n';
	return 0;
}

Compilation message

dna.cpp: In function 'int main()':
dna.cpp:28:18: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |   if(valid.size()==k){
      |      ~~~~~~~~~~~~^~~
dna.cpp:39:19: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |    if(valid.size()==k){
      |       ~~~~~~~~~~~~^~~

Subtask #1

16.0 / 16.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	492 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct

Subtask #2

24.0 / 24.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	4 ms	492 KB	Output is correct
4	Correct	7 ms	620 KB	Output is correct
5	Correct	3 ms	492 KB	Output is correct
6	Correct	2 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	27 ms	492 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	1 ms	364 KB	Output is correct

Subtask #3

28.0 / 28.0

#	결과	실행 시간	메모리	Grader output
1	Correct	49 ms	1588 KB	Output is correct
2	Correct	36 ms	1516 KB	Output is correct
3	Correct	22 ms	1516 KB	Output is correct
4	Correct	32 ms	1516 KB	Output is correct
5	Correct	277 ms	6380 KB	Output is correct
6	Correct	31 ms	1516 KB	Output is correct
7	Correct	30 ms	1644 KB	Output is correct
8	Correct	664 ms	12660 KB	Output is correct
9	Correct	51 ms	2700 KB	Output is correct
10	Correct	40 ms	1644 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	384 KB	Output is correct
13	Correct	4 ms	492 KB	Output is correct
14	Correct	6 ms	620 KB	Output is correct
15	Correct	4 ms	492 KB	Output is correct
16	Correct	2 ms	364 KB	Output is correct
17	Correct	1 ms	364 KB	Output is correct
18	Correct	1 ms	364 KB	Output is correct
19	Correct	1 ms	364 KB	Output is correct
20	Correct	1 ms	364 KB	Output is correct
21	Correct	1 ms	364 KB	Output is correct
22	Correct	1 ms	364 KB	Output is correct
23	Correct	1 ms	364 KB	Output is correct
24	Correct	1 ms	364 KB	Output is correct
25	Correct	0 ms	364 KB	Output is correct

Subtask #4

0 / 32.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1557 ms	7404 KB	Output is correct
2	Correct	1435 ms	6088 KB	Output is correct
3	Correct	537 ms	5868 KB	Output is correct
4	Correct	16 ms	1516 KB	Output is correct
5	Correct	114 ms	4972 KB	Output is correct
6	Execution timed out	2090 ms	13036 KB	Time limit exceeded
7	Halted	0 ms	0 KB	-