Submission #221395

#	Time	Username	Problem	Language	Result	Execution time	Memory
221395		anonymous	Fish (IOI08_fish)	C++14	49 / 100	3087 ms	33272 KiB

fish

#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#define MAXN 500005
#define fi first
#define se second
using namespace std;
int F, K, M, B[MAXN], Num[MAXN], Ans;
pair<int,int> Fish[MAXN];
vector<int> S[MAXN];
int main() {
    //freopen("fishin.txt","r",stdin);
    scanf("%d\n%d\n%d",&F,&K,&M);
    for (int i=1; i<=F; i++) {
        scanf("%d %d",&Fish[i].first, &Fish[i].second);
    }
    sort(Fish+1, Fish+F+1);
    for (int i=1; i<=F; i++) {
        B[Fish[i].se] = Fish[i].fi;
        S[Fish[i].se].push_back(Fish[i].fi);
    }
    for (int t1=1; t1<=K; t1++) {
        int nxt = 1e9 + 10;
        for (int i=1; i<=F; i++) {
            Num[i] = 0;
        }
        for (int i=1; i<=F; i++) {
            if (Fish[i].fi * 2 <= B[t1]) {
                Num[Fish[i].se] += 1;
            } else if (Fish[i].se == t1) {
                nxt = Fish[i].fi;
                break;
            }
        }
        Num[t1] += 1;
        int Max = 1, NonMax = 1;
        for (int t2=1; t2 <= K; t2 ++) {
            if (t1 == t2) {
                NonMax = (NonMax * (Num[t1] - 1)) %M;
            } else {
                if (B[t2] < 2*nxt) {
                    if (B[t2] < B[t1] || (B[t2] == B[t1] && t2 < t1)) {
                        NonMax = (NonMax * (Num[t2] + 1)) %M;
                    }
                    Max = (Max * (Num[t2] + 1)) % M;
                }
            }
        }
        //printf("%d %d %d %d\n",t1,nxt,Max,NonMax);
        Ans = (Ans + Max + NonMax) % M;
    }
    printf("%d", Ans);
}

Compilation message (stderr)

fish.cpp: In function 'int main()':
fish.cpp:14:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d\n%d\n%d",&F,&K,&M);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:16:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d",&Fish[i].first, &Fish[i].second);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 4 / 4
• Subtask 2: 4 / 4
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 6 / 6
• Subtask 8: 6 / 6
• Subtask 9: 6 / 6
• Subtask 10: 6 / 6
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 7
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5