Submission #788446

#	Time	Username	Problem	Language	Result	Execution time	Memory
788446		tatyam	Fish (IOI08_fish)	C++17	0 / 100	122 ms	7036 KiB

fish

#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];
        vector<bool> counted(jewel.A.begin(), jewel.A.end());
        jewel.del(J0);
        
        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
• Subtask 2: 0 / 4
• Subtask 3: 0 / 4
• Subtask 4: 0 / 4
• Subtask 5: 0 / 4
• Subtask 6: 0 / 5
• Subtask 7: 0 / 6
• Subtask 8: 0 / 6
• Subtask 9: 0 / 6
• Subtask 10: 0 / 6
• Subtask 11: 0 / 7
• Subtask 12: 0 / 7
• Subtask 13: 0 / 7
• Subtask 14: 0 / 5
• Subtask 15: 0 / 5
• Subtask 16: 0 / 5
• Subtask 17: 0 / 5
• Subtask 18: 0 / 5
• Subtask 19: 0 / 5