oj.uz

Submission #381863

# Submission time Handle Problem Language Result Execution time Memory
381863 2021-03-26T05:48:37 Z thecodingwizard Last supper (IOI12_supper) C++11
0 / 100
 558 ms 86644 KB 
#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]]++;
            count[addedTime[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 {
                assert(count[addedTime[toRemove.s.f]] == uses[toRemove.s.f]);
                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;
}

#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.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 68200 KB Output is correct
2 Correct 54 ms 68196 KB Output is correct
3 Correct 57 ms 68464 KB Output is correct
4 Correct 60 ms 68296 KB Output is correct
5 Correct 60 ms 68408 KB Output is correct
6 Runtime error 61 ms 68780 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 69164 KB Output is correct
2 Runtime error 181 ms 73192 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 77852 KB Output is correct
2 Correct 504 ms 81616 KB Output is correct
3 Correct 527 ms 82284 KB Output is correct
4 Correct 510 ms 82124 KB Output is correct
5 Correct 463 ms 80372 KB Output is correct
6 Correct 558 ms 82240 KB Output is correct
7 Correct 522 ms 82448 KB Output is correct
8 Correct 466 ms 82036 KB Output is correct
9 Runtime error 366 ms 86644 KB Execution killed with signal 6
10 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 68636 KB Output is correct
2 Correct 73 ms 68868 KB Output is correct
3 Runtime error 60 ms 68908 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Runtime error 441 ms 82928 KB Execution killed with signal 6
2 Correct 488 ms 79872 KB Output is correct - 122000 bits used
3 Correct 518 ms 81092 KB Output is correct - 125000 bits used
4 Correct 513 ms 81228 KB Output is correct - 125000 bits used
5 Correct 521 ms 81300 KB Output is correct - 125000 bits used
6 Correct 540 ms 80836 KB Output is correct - 125000 bits used
7 Correct 511 ms 80980 KB Output is correct - 124828 bits used
8 Correct 522 ms 80844 KB Output is correct - 124910 bits used
9 Correct 511 ms 80972 KB Output is correct - 125000 bits used
10 Correct 514 ms 80964 KB Output is correct - 125000 bits used