Submission #381859

#	Time	Username	Problem	Language	Result	Execution time	Memory
381859		thecodingwizard	Last supper (IOI12_supper)	C++11	0 / 100	376 ms	76244 KiB

advisor

#include <bits/stdc++.h>
#include "advisor.h"

using namespace std;

#define s second
#define f first

queue<int> nextUse[100000];

void ComputeAdvice(int *C, int N, int K, int M) {
    vector<int> uses(K, 0);
    for (int i = 0; i < N; i++) {
        //cout << "using " << C[i] << " at " << i << endl;
        nextUse[C[i]].push(i);
    }
    for (int i = 0; i < N; i++) {
        nextUse[i].push(N);
    }

    // first holds next use time, second holds k-index, third holds whether its among the first k
    set<pair<int, pair<int, int>>> stuff;
    set<int> inSet;
    map<int, int> pos;
    map<int, int> revPos;
    map<int, int> addedTime;
    for (int i = 0; i < K; i++) {
        //cout << "ADDING " << nextUse[i].front() << " " << i << " " << 1 << endl;
        stuff.insert(make_pair(nextUse[i].front(), make_pair(i, 1)));
        nextUse[i].pop();
        inSet.insert(i);
        pos[i] = i;
        revPos[i] = i;
    }

    int nextCt = 0;
    vector<int> count(N, 0);
    int timeCtr = K;
    for (int i = 0; i < N; i++) {
        //cout << "============ ";
        //for (int j = 0; j < K; j++) cout << revPos[j];
        //cout << " ============" << endl;
        int c = C[i];
        if (inSet.count(c)) {
            //cout << "used " << c << endl;
            uses[pos[c]]++;
        } else {
            while (stuff.begin()->f < i) {
                int c2 = revPos[stuff.begin()->s.f];
                while (!nextUse[c2].empty() && nextUse[c2].front() < i) nextUse[c2].pop();
                int nextTime = N;
                if (!nextUse[c2].empty()) {
                    nextTime = nextUse[c2].front(); nextUse[c2].pop();
                }
                pair<int, int> bkup = stuff.begin()->s;
                stuff.erase(stuff.begin());
                stuff.insert(make_pair(nextTime, bkup));
            }
            pair<int, pair<int, int>> toRemove = *stuff.rbegin();
            stuff.erase(--stuff.end());

            if (toRemove.s.s) {
                count[toRemove.s.f] = uses[toRemove.s.f];
            } else {
                count[addedTime[toRemove.s.f]] = uses[toRemove.s.f];
                nextCt++;
            }

            uses[toRemove.s.f] = 0;

            int removeColor = revPos[toRemove.s.f];
            //cout << "removing " << removeColor << " which is next used " << toRemove.f << endl;
            //cout << "and used " << c << endl;
            inSet.erase(removeColor);
            pos.erase(removeColor);

            revPos[toRemove.s.f] = c;
            inSet.insert(c);
            pos[c] = toRemove.s.f;
            int nextTime = N;
            if (!nextUse[c].empty()) {
                while (nextUse[c].front() <= i) nextUse[c].pop();
                nextTime = nextUse[c].front(); nextUse[c].pop();
            }
            stuff.insert(make_pair(nextTime, make_pair(toRemove.s.f, 0)));
            addedTime[toRemove.s.f] = timeCtr++;
        }
    }

    for (auto x : stuff) {
        if (x.s.s) count[x.s.f] = uses[x.s.f];
    }

    for (int i = 0; i < timeCtr; i++) {
        //cout << count[i] << " ";
        for (int j = 0; j < count[i]; j++) WriteAdvice(1);
        WriteAdvice(0);
    }
    cout << nextCt << "-------------------------" << endl;
    //cout << endl;
}

assistant

#include <bits/stdc++.h>
#include "assistant.h"

using namespace std;

#define f first
#define s second

void Assist(unsigned char *A, int N, int K, int R) {
    map<int, int> useLeft;
    int idx = 0;
    map<int, int> pos;
    map<int, int> revPos;
    queue<int> toRemove;
    for (int i = 0; i < K; i++) {
        int ct = 0;
        while (A[idx] != 0) {
            ct++;
            idx++;
        }
        idx++;
        useLeft[i] = ct;
        //cout << i << " will be used " << ct << " times " << endl;
        if (ct == 0) {
            toRemove.push(i);
            //cout << "ADDING " << i << endl;
        }
        pos[i] = i;
        revPos[i] = i;
    }

    for (int i = 0; i < N; i++) {
        int req = GetRequest();
        if (pos.count(req)) {
            useLeft[pos[req]]--;
            if (useLeft[pos[req]] == 0) {
                toRemove.push(pos[req]);
            }
        } else {
            if (toRemove.empty()) {
                for (int i = 0; i < K; i++) {
                    cout << i << ": " << revPos[i] << " " << useLeft[i] << ", ";
                }
                cout << endl;
                assert(!toRemove.empty());
            }
            int remove = toRemove.front(); toRemove.pop();
            //cout <<"REMOVING " << revPos[remove] << endl;
            PutBack(revPos[remove]);
            pos.erase(revPos[remove]);
            revPos[remove] = req;
            pos[req] = remove;
            int ct = 0;
            if (idx == R) {
                //cout << "RIP" << endl;
                ct = 10000000;
            } else {
                while (A[idx] != 0) {
                    ct++;
                    idx++;
                }
                idx++;
            }
            useLeft[remove] = ct;
            if (ct == 0) {
                toRemove.push(remove);
                //cout << "ADDING " << revPos[remove] << " x" << ct << endl;
            }
        }
    }
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 35
• Subtask 5: 0 / 39