# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
112574 | 2019-05-20T16:34:35 Z | user202729 | Fish (IOI08_fish) | C++17 | 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
# | 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 | 384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 356 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 | 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 | 195 ms | 3084 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 | 4 ms | 384 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 253 ms | 1704 KB | Output is correct |
2 | Correct | 188 ms | 1904 KB | Output is correct |
# | 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 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 3042 ms | 2424 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 3007 ms | 3576 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | 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 |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 3043 ms | 3448 KB | Time limit exceeded |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 3052 ms | 4236 KB | Time limit exceeded |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 3031 ms | 4216 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 3089 ms | 9164 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 3028 ms | 10232 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 3098 ms | 11612 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |