oj.uz

Submission #53801

# Submission time Handle Problem Language Result Execution time Memory
53801 2018-07-01T08:24:51 Z 강태규(#1435) Fish (IOI08_fish) C++11
0 / 100
 533 ms 4600 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

const int inf = 1e9 + 1;
int f, k, mod;
pii fs[500000];
int mx[500001];
int cnt[500001];
int ch[500001];

int main() {
    scanf("%d%d%d", &f, &k, &mod);
    if (k > 7000) return 0;
    for (int i = 0; i < f; ++i) {
        int l, x;
        scanf("%d%d", &l, &x);
        fs[i] = pii(l, x);
        ++cnt[x];
    }
    sort(fs, fs + f, greater<pii>());
    int ans = 0;
    for (int i = 0, j = 0; i < f; ++i) {
        if (ch[fs[i].second]) continue;
        while (j < f && 2 * fs[j].first > fs[i].first) {
            --cnt[fs[j].second];
            ++j;
        }
        llong mul = 1;
        for (int i = 1; i <= k; ++i) {
            if (ch[i] == 0) mul = mul * (cnt[i] + 1) % mod;
        }
        ans += mul;
        ans %= mod;
        if (i == 0) {
            for (int it = 1; it <= k; ++it) mx[it] = cnt[it];
        }
        else {
            if (cnt[fs[i].second] == mx[fs[i].second]) {
                llong mul1 = 1, mul2 = 1;
                for (int j = 1; j <= k; ++j) {
                    if (j == fs[i].second) continue;
                    mul1 = mul1 * (cnt[i] + 1) % mod;
                    if (ch[j] == 0) mul2 = mul2 * (cnt[i] + 1) % mod;
                }
                ans += mul1;
                ans += mod - mul2;
                ans %= mod;
            }
        }
        ch[fs[i].second] = 1;
    }
    
    printf("%d\n", ans);
	return 0;
}

Compilation message

fish.cpp: In function 'int main()':
fish.cpp:29:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d", &f, &k, &mod);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
fish.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &l, &x);
         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 248 KB Output isn't correct

Subtask #2
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 356 KB Output isn't correct

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 432 KB Output isn't correct

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 432 KB Output isn't correct

Subtask #5
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 508 KB Output is correct
2 Incorrect 2 ms 508 KB Output isn't correct

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 544 KB Output is correct
2 Incorrect 209 ms 4564 KB Output isn't correct

Subtask #7
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4564 KB Output isn't correct

Subtask #8
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 4564 KB Output isn't correct

Subtask #9
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 80 ms 4564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 4564 KB Output is correct
2 Incorrect 31 ms 4564 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #11
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 190 ms 4564 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 248 ms 4600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 533 ms 4600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4600 KB Output isn't correct

Subtask #15
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4600 KB Output isn't correct

Subtask #16
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #17
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #18
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #19
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4600 KB Output isn't correct
2 Halted 0 ms 0 KB -