제출 #112662

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
112662		user202729	Fish (IOI08_fish)	C++17	26 / 100	3098 ms	11508 KiB

fish

// https://oj.uz/problem/view/IOI08_fish
#include<iostream>
#include<vector>
#include<cassert>
#include<algorithm>

int main(){
	std::ios::sync_with_stdio(0);std::cin.tie(0);
	int nf,nk,mod;std::cin>>nf>>nk>>mod;
	assert(mod<=30000);
	std::vector<std::vector<int>> lenof(nk); // kind -> list of fish lengths
	for(int i=0;i<nf;++i){
		int len,kind;std::cin>>len>>kind;--kind;
		assert(len>0);
		lenof[kind].push_back(len);
	}
	for(int k=0;k<nk;++k){
		assert(!lenof[k].empty());
		std::sort(begin(lenof[k]),end(lenof[k]));
	}

	int ans=0;
	for(int k=0;k<nk;++k){
		// consider subsets with kind k being the max-kind
		auto const& ls=lenof[k];
		for(int a=0;a<ls.size();++a){ // assume there are a non-top gems of kind k
			int const l2=ls.back()/2; // all non-top fishes must have len <= l2

			if(a>0&&ls[a-1]>l2)
				break;

			// the max will always be ls.back() except for the last iteration
			int const lim=std::max(ls.back(),ls[a]*2);

			// if the subset has some z >= lim, then it can be moved to the top,
			// so (k) is not the max-kind. So we should only consider the values
			// that its top is <= k.

			// (note: because there may be multiple fishes with same length,
			// the kind number is used as the tie break)

			int cur=1; // number of valid subset for current (k,a) pair

			for(int z=0;z<nk;++z)if(z!=k){
				auto const& ls2=lenof[z];
				if(ls2.back()>lim||(ls2.back()==lim&&z>k)){
					// if z is in the subset, k is not maximal
					continue;
				}
				cur=(cur*(
					// number of values <= l2 (can be inside the subset) of kind z
					std::upper_bound(begin(ls2),end(ls2),l2)-begin(ls2)
					+1LL
					))%mod;
			}

			ans+=cur;
			ans%=mod;
		}
	}
	std::cout<<ans<<'\n';
}

/*
5 3 100
2 2
5 1
8 3
4 1
2 3


5 5 100
1 1
1 2
1 3
1 4
2 5

4 2 100
1 1
1 2
3 1
3 2


*/

컴파일 시 표준 에러 (stderr) 메시지

fish.cpp: In function 'int main()':
fish.cpp:26:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int a=0;a<ls.size();++a){ // assume there are a non-top gems of kind k
               ~^~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 6 / 6
• Subtask 10: 0 / 6
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 7
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5