oj.uz

답안 #112661

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
112661 2019-05-21T08:55:47 Z user202729 Fish (IOI08_fish) C++17
26 / 100
 3000 ms 15332 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; // 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);

			// 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){
				auto const& ls2=lenof[z];
				if(ls2.back()>lim||(ls2.back()==lim&&z>k))
					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
*/

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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #2
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct

Subtask #4
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct

Subtask #5
4.0 / 4.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 193 ms 7540 KB Output isn't correct

Subtask #7
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 384 KB Output isn't correct

Subtask #8
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 408 KB Output isn't correct

Subtask #9
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 377 ms 4128 KB Output is correct
2 Correct 263 ms 5104 KB Output is correct

Subtask #10
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 500 KB Output is correct
2 Correct 76 ms 512 KB Output is correct
3 Incorrect 98 ms 524 KB Output isn't correct

Subtask #11
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3098 ms 6452 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3094 ms 7460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 413 ms 6588 KB Output is correct
2 Execution timed out 3095 ms 7260 KB Time limit exceeded

Subtask #14
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3015 ms 7432 KB Time limit exceeded

Subtask #15
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3027 ms 8056 KB Time limit exceeded

Subtask #16
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3035 ms 8220 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3038 ms 13004 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3041 ms 14140 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3016 ms 15332 KB Time limit exceeded
2 Halted 0 ms 0 KB -