Submission #1206624

#	Time	Username	Problem	Language	Result	Execution time	Memory
1206624		ocean	Infinite Race (EGOI24_infiniterace2)	C++17	34 / 100	36 ms	1352 KiB

Main

#include <iostream>   
#include <vector>     
#include <cstdlib>    
using namespace std;

int main() {
    int N, Q;
    if (!(cin >> N >> Q)) return 0;

    /* state[p] : 1 = p is ahead of Anika, 0 = behind */
    vector<unsigned char> state(N, 1);
    /* lastEpoch[p] : last epoch when p was ahead of Anika */
    /* lastEpoch[p] = epoch + 1 means p was behind in this epoch */
    /* lastEpoch[p] = epoch means p was ahead in this epoch */
    vector<int>           lastEpoch(N, 0);

    long long epoch = 0;   // how many laps Anika has already run
    long long laps  = 0;   // answer we build

    while (Q--) {
        int x; cin >> x;
        int p = std::abs(x);      // runner index (1 … N-1)

        bool needAhead = (x > 0); // event requires: before it, p is ahead?

        /* current status of p */
        bool aheadNow = (lastEpoch[p] == epoch) ? state[p] : true;

        if (aheadNow != needAhead) {   // impossible ⇒ force one lap
            ++laps;
            ++epoch;                   // after a lap everybody is ahead
            aheadNow = true;
        }

        /* flip relative order according to the event */
        state[p]     = !needAhead;     // becomes behind or ahead
        lastEpoch[p] =  epoch;         // updated this epoch
    }

    cout << laps << '\n';
    return 0;
}

• Subtask 1: 0 / 29
• Subtask 2: 34 / 34
• Subtask 3: 0 / 22
• Subtask 4: 0 / 15