# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
221392 | anonymous | Fish (IOI08_fish) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<iostream>
#include<algorithm>
#include<utility>
#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;
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);
}