답안 #763702

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
763702 2023-06-22T16:14:00 Z Kripton Fish (IOI08_fish) C++14
4 / 100
3000 ms 5784 KB
#include <bits/stdc++.h>
using namespace std;

pair <int, int> v[500001];
int vf[500001], maxi[500001];
bitset <500001> checc;

int k, m;

int recalc()
{
    int rez = 1;
    for(int i = 1; i <= k; i++)
        if(!checc[i])
            rez = 1LL * rez * (vf[i] + 1) % m;
    return rez;
}

int recalc_fara(int j)
{
    int rez = 1;
    for(int i = 1; i <= k; i++)
        if(i != j)
            rez = 1LL * rez * (vf[i] + 1) % m;
    return rez;
}

int main()
{
#ifdef HOME
    freopen("test.in", "r", stdin);
    freopen("test.out", "w", stdout);
#endif // HOME
    int n;
    cin >> n >> k >> m;
    for(int i = 1; i <= n; i++)
        cin >> v[i].first >> v[i].second;
    sort(v + 1, v + n + 1);
    int j = 1;
    while(j <= n && 2 * v[j].first <= v[n].first)
    {
        vf[v[j].second]++;
        j++;
    }
    j--;
    for(int i = 1; i <= k; i++)
        maxi[i] = vf[i];
    int cate = 0;
    for(int i = n; i >= 1; i--)
    {
        while(j >= 1 && 2 * v[j].first > v[i].first)
        {
            vf[v[j].second]--;
            j--;
        }
        if(!checc[v[i].second])
        {
            if(vf[v[i].second] == maxi[v[i].second])
            {
                cate = (cate + recalc_fara(v[i].second)) % m;
                vf[v[i].second]--;
                cate = (cate + recalc()) % m;
                vf[v[i].second]++;
            }
            else
                cate = (cate + recalc()) % m;
            checc[v[i].second] = 1;
        }
    }
    cout << cate;
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 241 ms 4140 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 96 ms 1860 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 356 KB Output is correct
2 Incorrect 9 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 164 ms 2588 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 294 ms 4156 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 238 ms 2744 KB Output is correct
2 Incorrect 559 ms 4272 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 1087 ms 3920 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 2541 ms 4360 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3022 ms 3928 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3073 ms 4940 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3042 ms 5008 KB Time limit exceeded
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3053 ms 5784 KB Time limit exceeded
2 Halted 0 ms 0 KB -