oj.uz

Submission #283262

# Submission time Handle Problem Language Result Execution time Memory
283262 2020-08-25T12:55:03 Z alexandra_udristoiu Last supper (IOI12_supper) C++14
0 / 100
 106 ms 10480 KB 
#include<algorithm>
#include<set>
#include "advisor.h"
#define DIM 100005
#define f first
#define s second
using namespace std;
static int viz[DIM], nxt[DIM], ff[2 * DIM], p[DIM];
static set< pair<int, int> > h;
static set< pair<int, int> > :: iterator it;

void ComputeAdvice(int *c, int n, int k, int m) {
    int i;
    for(i = 0; i < n; i++){
        viz[i] = n;
    }
    for(i = n - 1; i >= 0; i--){
        nxt[i] = viz[ c[i] ];
        viz[ c[i] ] = i;
    }
    for(i = 0; i < k; i++){
        p[i] = i;
        h.insert( make_pair(-viz[i], i) );
    }
    for(i = 0; i < n; i++){
        if(i < k){
            viz[i] = 1;
        }
        else{
            viz[i] = 0;
        }
    }
    for(i = 0; i < n; i++){
        if(viz[ c[i] ] == 1){
            h.erase( make_pair(-i, c[i]) );
            p[ c[i] ] = i + k;
            h.insert( make_pair(-nxt[i], c[i]) );
            continue;
        }
        it = h.begin();
        viz[it->s] = 0;
        ff[ p[it->s] ] = 1;
        h.erase(it);
        p[ c[i] ] = i + k;
        h.insert( make_pair(-nxt[i], c[i]) );
    }
    for(i = 0; i < n + k; i++){
        WriteAdvice(ff[i]);
    }
}


#include "assistant.h"
#include<algorithm>
#define DIM 100005
using namespace std;
static int viz[DIM], w[2 * DIM];

void Assist(unsigned char *a, int n, int k, int r) {
    int i, x, nr = 0;
    for(i = 0; i < k; i++){
        viz[i] = 1;
        if(a[i] == 1){
            w[++nr] = i;
        }
    }
    for(i = 1; i <= n; i++){
        x = GetRequest();
        if(viz[x] == 0){
            PutBack(w[nr]);
            viz[ w[nr] ] = 0;
            nr--;
            viz[x] = 1;
        }
        if(a[i + k - 1] == 1){
            w[++nr] = x;
        }
    }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 904 KB Output is correct
2 Incorrect 0 ms 1164 KB Output isn't correct - not an optimal way
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 1536 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 8176 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1144 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 9712 KB Output isn't correct - not an optimal way
2 Incorrect 99 ms 9968 KB Output isn't correct - not an optimal way
3 Incorrect 103 ms 10224 KB Output isn't correct - not an optimal way
4 Incorrect 104 ms 10480 KB Output isn't correct - not an optimal way
5 Incorrect 104 ms 10224 KB Output isn't correct - not an optimal way
6 Incorrect 106 ms 10296 KB Output isn't correct - not an optimal way
7 Incorrect 104 ms 10224 KB Output isn't correct - not an optimal way
8 Incorrect 105 ms 10224 KB Output isn't correct - not an optimal way
9 Incorrect 103 ms 10224 KB Output isn't correct - not an optimal way
10 Correct 102 ms 10224 KB Output is correct - 125000 bits used