| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 501804 |
2022-01-04T15:41:43 Z |
600Mihnea |
Fish (IOI08_fish) |
C++17 |
|
3000 ms |
25592 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() << "\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 |
6 ms |
11980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
11980 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
399 ms |
12108 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
827 ms |
14032 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3043 ms |
11980 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
11980 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
11980 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
12108 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
59 ms |
15676 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
12180 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
210 ms |
17604 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
171 ms |
21064 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
368 ms |
17568 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3069 ms |
20356 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3078 ms |
21540 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3062 ms |
19904 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3056 ms |
23380 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3020 ms |
24184 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
3065 ms |
25592 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
