| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 501807 |
2022-01-04T15:42:06 Z |
600Mihnea |
Fish (IOI08_fish) |
C++17 |
|
3000 ms |
25200 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Guy {
int sz;
int type;
};
bool operator < (Guy a, Guy b) {
return a.sz < b.sz;
}
const int N = (int) 5e5 + 7;
int n, k, mod, pref[N];
Guy a[N];
vector<int> where[N];
int getCnt(int prefix, int type) {
assert(0 <= prefix && prefix <= n);
assert(1 <= type && type <= k);
int sol = 0;
int low = 0, high = (int) where[type].size() - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (where[type][mid] <= prefix) {
sol = mid + 1;
low = mid + 1;
} else {
high = mid - 1;
}
}
return sol;
}
int solve() {
int sol = 0;
set<vector<int>> all;
for (int mask = 1; mask < (1 << n); mask++) {
vector<int> current;
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
current.push_back(i + 1);
}
}
int sz = (int) current.size();
if (sz >= 2) {
bool ok = 1;
ok &= (a[current[sz - 1]].sz >= 2 * a[current[sz - 2]].sz);
if (!ok) {
continue;
}
}
vector<int> total;
for (auto &x : current) {
total.push_back(a[x].type);
}
sort(total.begin(), total.end());
all.insert(total);
}
return (int) all.size();
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
/// freopen ("input", "r", stdin);
cin >> n >> k >> mod;
for (int i = 1; i <= n; i++) {
cin >> a[i].sz >> a[i].type;
}
sort(a + 1, a + n + 1);
for (int i = 1; i <= n; i++) {
where[a[i].type].push_back(i);
}
vector<int> potential;
for (int i = 1; i <= k; i++) {
assert(!where[i].empty());
if (where[i].back() != n) {
potential.push_back(where[i].back());
}
}
{
int pt = 0;
for (int i = 1; i <= n; i++) {
while (pt + 1 <= n && a[pt + 1].sz * 2 <= a[i].sz) {
pt++;
}
assert(pt < i);
pref[i] = pt;
}
}
sort(potential.begin(), potential.end());
assert((int) potential.size() == k - 1);
int print = 0;
{
/// for the last one it is quite easy
int sol = 1;
for (int i = 1; i <= k; i++) {
int frq = getCnt(pref[n], i);
sol = sol * (ll) (frq + 1) % mod;
}
print += sol;
if (print >= mod) {
print -= mod;
}
}
sort(potential.begin(), potential.end());
assert((int) potential.size() == k - 1);
for (int step = (int) potential.size() - 1; step >= 0; step--) {
int ind = potential[step];
if (getCnt(pref[ind], a[ind].type) + 1 <= getCnt(pref[n], a[ind].type)) {
/// it is only useful when we cast smaller guys than him
int sol = 1;
for (int s = 0; s <= step; s++) {
int frq = getCnt(pref[ind], a[potential[s]].type);
sol = sol * (ll) (frq + 1) % mod;
}
print += sol;
if (print >= mod) {
print -= mod;
}
} else {
/// et extra when Il y a maximum
{
int sol = 1;
for (int s = 0; s < step; s++) {
int frq = getCnt(pref[ind], a[potential[s]].type);
sol = sol * (ll) (frq + 1) % mod;
}
{
int frq = getCnt(pref[ind], a[potential[step]].type);
sol = sol * (ll) frq % mod;
}
print += sol;
if (print >= mod) {
print -= mod;
}
}
int sol = 1;
for (int i = 1; i <= k; i++) {
if (i == a[ind].type) {
continue; /// no choice
}
int frq = getCnt(pref[ind], i);
sol = sol * (ll) (frq + 1) % mod;
}
print += sol;
if (print >= mod) {
print -= mod;
}
}
}
cout << solve() % mod << "\n";
exit(0);
cout << print << "\n";
return 0;
}
/**
: [1] [1,2] [2]
**/
Compilation message
fish.cpp: In function 'int solve()':
fish.cpp:39:7: warning: unused variable 'sol' [-Wunused-variable]
39 | int sol = 0;
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
12068 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
12096 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
460 ms |
12112 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1004 ms |
14028 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3080 ms |
11980 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
12068 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
12020 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
12116 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
55 ms |
15924 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
12080 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
208 ms |
17888 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
167 ms |
21268 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
356 ms |
17728 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3084 ms |
20576 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3095 ms |
21700 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3060 ms |
19984 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3041 ms |
23428 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3037 ms |
24308 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3088 ms |
25200 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
