oj.uz

Submission #788445

# Submission time Handle Problem Language Result Execution time Memory
788445 2023-07-20T08:42:44 Z tatyam Fish (IOI08_fish) C++17
0 / 100
 125 ms 14840 KB 
#include <bits/stdc++.h>
using namespace std;

int M;
struct mint {
    int x = 0;
    mint& operator+=(mint a) {
        x += a.x;
        if(x >= M) x -= M;
        return *this;
    }
    mint operator+(mint a) const {
        return mint{*this} += a;
    }
};

struct Counter {
    vector<int> A;
    int kind = 0;
    Counter(int n): A(n) {}
    void add(int x) { if(A[x]++ == 0) kind++; }
    void del(int x) { if(--A[x] == 0) kind--; }
};

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int F, K;
    cin >> F >> K >> M;
    vector<pair<int, int>> fish(F);
    for(auto& [L, J] : fish) {
        cin >> L >> J;
        J--;
    }
    sort(fish.begin(), fish.end(), greater<>{});
    
    vector<mint> pow2(F + 1);
    pow2[0] = {1};
    for(int i = 0; i < F; i++) pow2[i + 1] = pow2[i] + pow2[i];
    
    mint ans = {0};
    while(fish.size()) {
        const auto [L0, J0] = fish[0];
        const auto half = partition_point(fish.begin(), fish.end(), [L0 = L0](pair<int, int> f) { return f.first * 2 > L0; });
        Counter jewel(K);
        
        for_each(half, fish.end(), [&, L0 = L0](pair<int, int> f) { auto [L, J] = f; if(L * 2 <= L0) jewel.add(J); });
        jewel.add(J0);
        ans += pow2[jewel.kind - 1];
        jewel.del(J0);
        
        vector<bool> counted(jewel.A.begin(), jewel.A.end());
        for(auto p = fish.begin(), q = half; p != fish.end(); p++) {
            const auto [L1, J1] = *p;
            if(L1 * 2 <= L0) break;
            if(counted[J1]) continue;
            while(q != fish.end()) {
                const auto [L2, J2] = *q;
                if(L2 * 2 > L1) {
                    jewel.del(J2);
                    q++;
                }
                else break;
            }
            jewel.add(J1);
            ans += pow2[jewel.kind - 1];
            jewel.del(J1);
            counted[J1] = 1;
        }
        
        fish.erase(remove_if(fish.begin(), fish.end(), [&](pair<int, int> f) { return counted[f.second]; }), fish.end());
    }
    
    cout << ans.x << endl;
}

Subtask #1
0 / 4.0

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

Subtask #2
0 / 4.0

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

Subtask #3
0 / 4.0

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

Subtask #4
0 / 4.0

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

Subtask #5
0 / 4.0

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

Subtask #6
0 / 5.0

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

Subtask #7
0 / 6.0

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

Subtask #8
0 / 6.0

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

Subtask #9
0 / 6.0

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

Subtask #10
0 / 6.0

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

Subtask #11
0 / 7.0

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

Subtask #12
0 / 7.0

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

Subtask #13
0 / 7.0

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

Subtask #14
0 / 5.0

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

Subtask #15
0 / 5.0

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

Subtask #16
0 / 5.0

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

Subtask #17
0 / 5.0

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

Subtask #18
0 / 5.0

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

Subtask #19
0 / 5.0

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