답안 #53832 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
53832	2018-07-01T09:07:15 Z	노영훈(#1436)	Fish (IOI08_fish)	C++11	0 / 100	6 ms	1324 KB

fish

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=7010, inf=2e9;
int mod;
int n, k;

struct fish {
    int l, c;
    bool operator < (const fish &f) const {
        return l<f.l;
    }
} F[MX];

int pw(int a, int e){
    if(e==0) return 1;
    int t=pw(a,e/2); t=t*t%mod;
    return (e%2==1 ? t*a%mod : t);
}

int inv(int x){
    return pw(x,mod-2);
    for(int i=0; i<mod; i++)
        if(1LL*i*x%mod==1) return i;
    return 0;
}

vector<int> P[MX];

uint16_t D[MX], E[MX];

void init(){
    // includes empty
    D[1]=2;
    for(int i=2; i<=n; i++){
        int c=F[i].c;
        int cnt=upper_bound(P[c].begin(), P[c].end(), i-1)-P[c].begin();
        if(cnt==0) D[i]=(D[i-1]*2)%mod;
        else D[i]=(D[i-1]+D[i-1]*inv(cnt+1))%mod;
    }
}

int find(int x){
    int s=0, e=n;
    while(s<e){
        int m=(s+e+1)/2;
        if(F[m].l*2<=x) s=m;
        else e=m-1;
    }
    return s;
}

int getn(){
    int r=find(F[n].l);
    int c=F[n].c;
    int cnt=upper_bound(P[c].begin(), P[c].end(), r)-P[c].begin();
    if(cnt==0) return D[r]*2%mod;
    else return 1LL*D[r]*inv(cnt+1)%mod;
}

int get(int i){
    int r=find(F[i].l);
    int c=F[i].c;
    int cnt=upper_bound(P[c].begin(), P[c].end(), r)-P[c].begin();
    if(cnt==0) return D[r]*2%mod;
    else return 1LL*D[r]*inv(cnt+1)%mod;
}


int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>n>>k>>mod;
    for(int i=1; i<=n; i++){
        int l,c; cin>>l>>c;
        F[i]={l,c};
    }
    sort(F+1, F+n+1);
    for(int i=1; i<=n; i++)
        P[F[i].c].push_back(i);
    init();
    int ans=getn();
    for(int i=1; i<=n; i++){
        if(F[i].l*2<=F[n].l) continue;
        if(F[i].c==F[n].c) continue;
        ans=(ans+get(i))%mod;
    }
    cout<<(ans+mod-1)%mod;


    return 0;
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	3 ms	672 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	3 ms	672 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 6.0

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

Subtask #8
0 / 6.0

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

Subtask #9
0 / 6.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	4 ms	792 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 6.0

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

Subtask #11
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	5 ms	800 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #12
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	4 ms	876 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #13
0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Incorrect	5 ms	880 KB	Output isn't correct
2	Halted	0 ms	0 KB	-

Subtask #14
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	6 ms	1260 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #15
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	5 ms	1324 KB	Execution killed with signal 11 (could be triggered by violating memory limits)

Subtask #16
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	5 ms	1324 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #17
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	5 ms	1324 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #18
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	4 ms	1324 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

Subtask #19
0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	5 ms	1324 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
2	Halted	0 ms	0 KB	-

답안 #53832

Compilation message