oj.uz

Submission #112574

# Submission time Handle Problem Language Result Execution time Memory
112574 2019-05-20T16:34:35 Z user202729 Fish (IOI08_fish) C++17
26 / 100
 3000 ms 11612 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(),ls[a]*2);

			// for all z > lim || (z == lim && index(z) > index(k)) and
			// z != k, it should not appear in the subset
			// (note: because there may be multiple fishes with same length,
			// the kind number the s 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){
				if(lenof[z].back()>lim||(
							lenof[z].back()==lim&&z>k))
					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


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

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 356 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
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 195 ms 3084 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 4 ms 384 KB Output isn't correct

Subtask #9
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 253 ms 1704 KB Output is correct
2 Correct 188 ms 1904 KB Output is correct

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 512 KB Output is correct
2 Correct 49 ms 504 KB Output is correct
3 Incorrect 64 ms 472 KB Output isn't correct

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3042 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 3007 ms 3576 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 313 ms 2648 KB Output is correct
2 Execution timed out 3044 ms 3316 KB Time limit exceeded

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3052 ms 4236 KB Time limit exceeded

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3031 ms 4216 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 3089 ms 9164 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 3028 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 3098 ms 11612 KB Time limit exceeded
2 Halted 0 ms 0 KB -