oj.uz

Submission #153116

# Submission time Handle Problem Language Result Execution time Memory
153116 2019-09-12T13:15:47 Z popovicirobert Last supper (IOI12_supper) C++14
0 / 100
 196 ms 7860 KB 
#include <bits/stdc++.h>
#include "advisor.h"

using namespace std;


void ComputeAdvice(int *C, int n, int k, int M) {

    vector <int> last(n, n), nxt(n);
    int i;

    for(i = n - 1; i >= 0; i--) {
        nxt[i] = last[C[i]];
        last[C[i]] = i;
    }

    set < pair <int, int> > pq;
    vector <int> pos(n, -1);

    for(i = 0; i < k; i++) {
        pq.insert({last[i], i});
        pos[i] = i;
    }

    vector <unsigned char> sol(n + k, 0);
    for(i = 0; i < n; i++) {
        if(pos[C[i]] != -1) {
            sol[pos[C[i]]] = 1;
            pq.erase(pq.lower_bound({i, -1}));
        }
        else {
            pos[prev(pq.end()) -> second] = -1;
            pq.erase(prev(pq.end()));
        }
        pq.insert({nxt[i], i + k});
        /*for(auto it : pq) {
            cerr << it.first << " " << it.second << "\n";
        }
        cerr << "\n";*/
        pos[C[i]] = i + k;
    }

    for(auto it : sol) {
        WriteAdvice(it);
    }
}

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

using namespace std;

void Assist(unsigned char *A, int n, int k, int R) {
    set <int> col, bad;
    int i;

    /*cerr << n + k << "\n";
    for(i = 0; i < n + k; i++) {
        cerr << (int) A[i] << " ";
    }*/

    for(i = 0; i < k; i++) {
        col.insert(i);
        if(A[i] == 0) {
            bad.insert(i);
        }
    }

    for(i = k; i < n + k; i++) {
        int cur = GetRequest();
        if(col.count(cur) == 0) {
            PutBack(*bad.begin());
            col.erase(*bad.begin());
            bad.erase(bad.begin());
        }
        if(A[i] == 0) {
            bad.insert(cur);
        }
        col.insert(cur);
    }

}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 760 KB Output is correct
2 Runtime error 3 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 888 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 49 ms 2816 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Runtime error 58 ms 3440 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 60 ms 3616 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 70 ms 3520 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Incorrect 190 ms 7496 KB Output isn't correct - not an optimal way
5 Incorrect 196 ms 7860 KB Output isn't correct - not an optimal way
6 Runtime error 64 ms 3452 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Incorrect 188 ms 7480 KB Output isn't correct - not an optimal way
8 Runtime error 70 ms 3616 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Incorrect 188 ms 7608 KB Output isn't correct - not an optimal way
10 Runtime error 51 ms 3456 KB Execution killed with signal 11 (could be triggered by violating memory limits)