# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
53733 |
2018-07-01T06:09:20 Z |
윤교준(#1438) |
Fish (IOI08_fish) |
C++11 |
|
1147 ms |
8760 KB |
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define rb(x) ((x)&(-(x)))
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAXN = 500005;
const int MAXK = 22;
int D[MAXK][MAXK];
int MXB[MAXK], MNB[MAXK];
int A[MAXN], B[MAXN];
ll Ans;
int N, K, MOD;
int main() {
ios::sync_with_stdio(false);
cin >> N >> K >> MOD;
for(int i = 1; i <= N; i++) cin >> B[i] >> A[i];
fill(MNB+1, MNB+K+1, INF);
for(int i = 1; i <= N; i++) {
upmax(MXB[A[i]], B[i]);
upmin(MNB[A[i]], B[i]);
}
for(int i = 1; i <= K; i++) {
for(int j = 1; j <= N; j++)
if(B[j]*2 <= MXB[i])
D[i][A[j]]++;
}
for(int key = 1; key < (1<<K); key++) {
int s[MAXK], e[MAXK];
int kc = 0;
fill(s, s+MAXK, 0); fill(e, e+MAXK, INF);
for(int i = 0; i < K; i++) if(key & (1<<i)) {
kc++;
for(int j = 1; j <= K; j++) {
int ss = 0, ee = D[i+1][j];
if(i+1 == j) { ss++; ee++; }
upmax(s[j], ss);
upmin(e[j], ee);
}
}
ll ret = 1;
for(int i = 1; i <= K; i++) {
if(s[i] > e[i]) ret = 0;
else ret = ret * (e[i]-s[i]+1) % MOD;
}
if(kc&1) Ans = (Ans + ret) % MOD;
else Ans = ((Ans - ret) % MOD + MOD) % MOD;
}
cout << Ans << endl;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
484 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
40 ms |
620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
620 KB |
Output is correct |
2 |
Correct |
27 ms |
620 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
620 KB |
Output is correct |
2 |
Correct |
1147 ms |
4436 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
3 ms |
4436 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
713 ms |
4436 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
330 ms |
4436 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
5 ms |
4436 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
317 ms |
5576 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
197 ms |
8744 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
262 ms |
8744 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
124 ms |
8744 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
128 ms |
8760 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
110 ms |
8760 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
122 ms |
8760 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
107 ms |
8760 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
141 ms |
8760 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
2 |
Halted |
0 ms |
0 KB |
- |