oj.uz

Submission #381864

# Submission time Handle Problem Language Result Execution time Memory
381864 2021-03-26T05:51:08 Z thecodingwizard Last supper (IOI12_supper) C++11
100 / 100
 614 ms 86120 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;
        addedTime[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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 68196 KB Output is correct
2 Correct 54 ms 68068 KB Output is correct
3 Correct 57 ms 68708 KB Output is correct
4 Correct 59 ms 68296 KB Output is correct
5 Correct 60 ms 68104 KB Output is correct
6 Correct 64 ms 68248 KB Output is correct
7 Correct 64 ms 68532 KB Output is correct
8 Correct 69 ms 68528 KB Output is correct
9 Correct 69 ms 68916 KB Output is correct
10 Correct 69 ms 68916 KB Output is correct
11 Correct 69 ms 68984 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 69304 KB Output is correct
2 Correct 208 ms 71100 KB Output is correct
3 Correct 614 ms 86120 KB Output is correct
4 Correct 232 ms 72204 KB Output is correct
5 Correct 294 ms 72496 KB Output is correct
6 Correct 402 ms 74444 KB Output is correct
7 Correct 500 ms 79780 KB Output is correct
8 Correct 430 ms 81260 KB Output is correct
9 Correct 186 ms 72196 KB Output is correct
10 Correct 560 ms 83968 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 77920 KB Output is correct
2 Correct 540 ms 80668 KB Output is correct
3 Correct 544 ms 81144 KB Output is correct
4 Correct 526 ms 80948 KB Output is correct
5 Correct 475 ms 79104 KB Output is correct
6 Correct 534 ms 81140 KB Output is correct
7 Correct 529 ms 81296 KB Output is correct
8 Correct 507 ms 81048 KB Output is correct
9 Correct 417 ms 81156 KB Output is correct
10 Correct 573 ms 82268 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 68748 KB Output is correct
2 Correct 68 ms 68744 KB Output is correct
3 Correct 62 ms 68104 KB Output is correct
4 Correct 64 ms 68272 KB Output is correct
5 Correct 63 ms 68400 KB Output is correct
6 Correct 64 ms 68636 KB Output is correct
7 Correct 66 ms 68748 KB Output is correct
8 Correct 68 ms 68672 KB Output is correct
9 Correct 73 ms 68932 KB Output is correct
10 Correct 73 ms 69864 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 488 ms 78908 KB Output is correct - 120000 bits used
2 Correct 537 ms 79900 KB Output is correct - 122000 bits used
3 Correct 524 ms 81020 KB Output is correct - 125000 bits used
4 Correct 520 ms 81264 KB Output is correct - 125000 bits used
5 Correct 558 ms 81028 KB Output is correct - 125000 bits used
6 Correct 521 ms 81148 KB Output is correct - 125000 bits used
7 Correct 535 ms 81080 KB Output is correct - 124828 bits used
8 Correct 541 ms 81024 KB Output is correct - 124910 bits used
9 Correct 529 ms 81012 KB Output is correct - 125000 bits used
10 Correct 523 ms 81028 KB Output is correct - 125000 bits used