oj.uz

Submission #112573

# Submission time Handle Problem Language Result Execution time Memory
112573 2019-05-20T16:23:22 Z user202729 Fish (IOI08_fish) C++17
27 / 100
 3000 ms 11800 KB 
// 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

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 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 384 KB Output is correct

Subtask #4
4.0 / 4.0

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

Subtask #5
0 / 4.0

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

Subtask #6
5.0 / 5.0

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

Subtask #7
0 / 6.0

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

Subtask #8
0 / 6.0

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

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 254 ms 1968 KB Output is correct
2 Correct 187 ms 5104 KB Output is correct

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 548 KB Output is correct
2 Correct 50 ms 512 KB Output is correct
3 Incorrect 70 ms 512 KB Output isn't correct

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3088 ms 2708 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 3018 ms 3804 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 2936 KB Output is correct
2 Execution timed out 3025 ms 3680 KB Time limit exceeded

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3032 ms 3832 KB Time limit exceeded

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3027 ms 4500 KB Time limit exceeded

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3099 ms 4472 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 3016 ms 9464 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 3018 ms 10540 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 3049 ms 11800 KB Time limit exceeded
2 Halted 0 ms 0 KB -