# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
112662 |
2019-05-21T09:16:49 Z |
user202729 |
Fish (IOI08_fish) |
C++17 |
|
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
~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
2 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
362 ms |
1656 KB |
Output is correct |
2 |
Correct |
249 ms |
1872 KB |
Output is correct |
# |
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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3009 ms |
2424 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3093 ms |
3540 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3028 ms |
3448 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3021 ms |
4300 KB |
Time limit exceeded |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3037 ms |
4308 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3049 ms |
9084 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3051 ms |
10232 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3042 ms |
11508 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |