oj.uz

Submission #283296

# Submission time Handle Problem Language Result Execution time Memory
283296 2020-08-25T13:53:37 Z alexandra_udristoiu Last supper (IOI12_supper) C++14
100 / 100
 143 ms 11232 KB 
#include<algorithm>
#include<set>
#include<iostream>
#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], nr;
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]) );
        viz[ c[i] ] = 1;
        nr++;
    }
    for(i = 0; i < n + k; i++){
        WriteAdvice(ff[i]);
    }
}


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

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;
        }
    }
}

Compilation message

assistant.cpp:6:34: warning: 'tot' defined but not used [-Wunused-variable]
    6 | static int viz[DIM], w[2 * DIM], tot = 0;
      |                                  ^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 904 KB Output is correct
2 Correct 1 ms 904 KB Output is correct
3 Correct 3 ms 912 KB Output is correct
4 Correct 3 ms 824 KB Output is correct
5 Correct 5 ms 1292 KB Output is correct
6 Correct 5 ms 1104 KB Output is correct
7 Correct 6 ms 1172 KB Output is correct
8 Correct 6 ms 1116 KB Output is correct
9 Correct 7 ms 1124 KB Output is correct
10 Correct 6 ms 1280 KB Output is correct
11 Correct 6 ms 1104 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1536 KB Output is correct
2 Correct 52 ms 4608 KB Output is correct
3 Correct 121 ms 11232 KB Output is correct
4 Correct 73 ms 7408 KB Output is correct
5 Correct 77 ms 7664 KB Output is correct
6 Correct 90 ms 8176 KB Output is correct
7 Correct 110 ms 9712 KB Output is correct
8 Correct 89 ms 9200 KB Output is correct
9 Correct 72 ms 7408 KB Output is correct
10 Correct 138 ms 10736 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 8248 KB Output is correct
2 Correct 116 ms 9968 KB Output is correct
3 Correct 143 ms 10152 KB Output is correct
4 Correct 115 ms 10080 KB Output is correct
5 Correct 120 ms 9984 KB Output is correct
6 Correct 128 ms 10352 KB Output is correct
7 Correct 118 ms 10200 KB Output is correct
8 Correct 114 ms 10080 KB Output is correct
9 Correct 103 ms 9456 KB Output is correct
10 Correct 121 ms 10192 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1164 KB Output is correct
2 Correct 6 ms 1024 KB Output is correct
3 Correct 5 ms 1024 KB Output is correct
4 Correct 5 ms 1104 KB Output is correct
5 Correct 5 ms 1024 KB Output is correct
6 Correct 5 ms 1160 KB Output is correct
7 Correct 6 ms 1156 KB Output is correct
8 Correct 7 ms 1132 KB Output is correct
9 Correct 7 ms 1116 KB Output is correct
10 Correct 9 ms 1536 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 9712 KB Output is correct - 120000 bits used
2 Correct 124 ms 9968 KB Output is correct - 122000 bits used
3 Correct 124 ms 10232 KB Output is correct - 125000 bits used
4 Correct 136 ms 10224 KB Output is correct - 125000 bits used
5 Correct 112 ms 10224 KB Output is correct - 125000 bits used
6 Correct 112 ms 10224 KB Output is correct - 125000 bits used
7 Correct 115 ms 10224 KB Output is correct - 124828 bits used
8 Correct 122 ms 10320 KB Output is correct - 124910 bits used
9 Correct 120 ms 10224 KB Output is correct - 125000 bits used
10 Correct 102 ms 10168 KB Output is correct - 125000 bits used