oj.uz

Submission #112662

# Submission time Handle Problem Language Result Execution time Memory
112662 2019-05-21T09:16:49 Z user202729 Fish (IOI08_fish) C++17
26 / 100
 3000 ms 11508 KB 
// 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


*/

Compilation message

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.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct

Subtask #2
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 432 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 199 ms 2984 KB Output isn't correct

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 384 KB Output isn't correct

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 362 ms 1656 KB Output is correct
2 Correct 249 ms 1872 KB Output is correct

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 496 KB Output is correct
2 Correct 73 ms 504 KB Output is correct
3 Incorrect 95 ms 512 KB Output isn't correct

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3009 ms 2424 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3093 ms 3540 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 432 ms 2552 KB Output is correct
2 Execution timed out 3098 ms 3440 KB Time limit exceeded

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3028 ms 3448 KB Time limit exceeded

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3021 ms 4300 KB Time limit exceeded

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3037 ms 4308 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3049 ms 9084 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3051 ms 10232 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3042 ms 11508 KB Time limit exceeded
2 Halted 0 ms 0 KB -