Submission #112573

#	Time	Username	Problem	Language	Result	Execution time	Memory
112573		user202729	Fish (IOI08_fish)	C++17	27 / 100	3099 ms	11800 KiB

fish

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

int main(){
	std::ios::sync_with_stdio(0);std::cin.tie(0);
	int nf,nk,mod;std::cin>>nf>>nk>>mod;
	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;
		lenof[kind].push_back(len);
	}
	for(int k=0;k<nk;++k)
		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; // the subset should contain only values <= l2

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

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

			// for all z >= lim, z != k, it should not appear in the subset

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


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

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

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

Compilation message (stderr)

fish.cpp: In function 'int main()':
fish.cpp:21: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: 0 / 4
• Subtask 6: 5 / 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