oj.uz

답안 #381842

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
381842 2021-03-26T04:45:01 Z thecodingwizard 최후의 만찬 (IOI12_supper) C++11
0 / 100
 2500 ms 141568 KB 
#include <bits/stdc++.h>
#include "advisor.h"

using namespace std;

#define s second
#define f first

void ComputeAdvice(int *C, int N, int K, int M) {
    vector<int> uses(K, 0);
    queue<int> nextUse[N];
    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;
    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;
    }

    vector<int> count(K, 0);
    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].front() < i) nextUse[c2].pop();
                int 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.push_back(uses[toRemove.s.f]);
            }

            uses[toRemove.s.f] = 0;

            inSet.erase(toRemove.f);
            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;
            while (nextUse[c].front() <= i) nextUse[c].pop();
            int nextTime = nextUse[c].front(); nextUse[c].pop();
            stuff.insert(make_pair(nextTime, make_pair(toRemove.s.f, 0)));
        }
    }

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

    for (int i = 0; i < count.size(); i++) {
        cout << count[i] << " ";
        for (int j = 0; j < count[i]; j++) WriteAdvice(1);
        WriteAdvice(0);
    }
    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);
        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 {
            int remove = toRemove.front(); toRemove.pop();
            PutBack(revPos[remove]);
            pos.erase(revPos[remove]);
            revPos[remove] = req;
            pos[req] = remove;
            int ct = 0;
            if (idx == R) {
                ct = 10000000;
            } else {
                while (A[idx] != 0) {
                    ct++;
                    idx++;
                }
                idx++;
            }
            useLeft[remove] = ct;
            if (ct == 0) {
                toRemove.push(remove);
            }
        }
    }
}

Compilation message

advisor.cpp: In function 'void ComputeAdvice(int*, int, int, int)':
advisor.cpp:83:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for (int i = 0; i < count.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2 ms 984 KB Error - Invalid Access
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 826 ms 38880 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2580 ms 128156 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 555 ms 36400 KB Error - Invalid Access
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2574 ms 141568 KB Time limit exceeded
2 Execution timed out 2565 ms 137648 KB Time limit exceeded
3 Execution timed out 2590 ms 137988 KB Time limit exceeded
4 Execution timed out 2591 ms 138092 KB Time limit exceeded
5 Execution timed out 2566 ms 137488 KB Time limit exceeded
6 Execution timed out 2581 ms 137396 KB Time limit exceeded
7 Execution timed out 2576 ms 138756 KB Time limit exceeded
8 Execution timed out 2571 ms 135724 KB Time limit exceeded
9 Execution timed out 2601 ms 139500 KB Time limit exceeded
10 Execution timed out 2601 ms 139536 KB Time limit exceeded