oj.uz

Submission #430120

# Submission time Handle Problem Language Result Execution time Memory
430120 2021-06-16T11:35:04 Z someone Last supper (IOI12_supper) C++14
0 / 100
 451 ms 87196 KB 
#include "advisor.h"
#include <bits/stdc++.h>
using namespace std;

struct Val {
    int i, val;

    bool operator <(const Val& v) const {
        return val > v.val;
    }
};

const int N = 1e5 + 10, INF = 1e9;

bool on[N];
char ch[] = {'0', '1'};
deque<int> pos[N], v[2];
int n1, m1, k1, c[N], nbbits1;

void addId(int i, int val, int bits) {
    if(bits == 0)
        return;
    addId(i, val/2, bits-1);
    v[i].push_back(val % 2);
    //cout << val % 2;
}

void compute(int id) {
    set<Val> last;
    vector<int> suppr;
    for(int i = 0; i < n1; i++) {
        on[i] = false;
        pos[i].clear();
    }
    for(int i = 0; i < n1; i++)
        pos[c[i]].push_back(i);
    for(int i = 0; i < k1; i++) {
        if(id == 1) {
            if(pos[i].size() == 0)
                v[id].push_back(1);
            else
                v[id].push_back(0);
        }
        on[i] = true;
        last.insert({i, pos[i][0]});
    }
    for(int i = 0; i < n1; i++)
        pos[i].push_back(INF);

    for(int i = 0; i < n1; i++) {
        if(!on[c[i]]) {
            on[c[i]] = true;
            auto it = last.end();
            it--;
            if(id == 1) {
                if(pos[c[i]][0] == INF) {
                    v[id].push_back(1);
                    //cout << 1 << ' ';
                } else {
                    v[id].push_back(0);
                    //cout << 0 << ' ';
                }
                if(suppr.empty()) {
                    addId(id, (*it).i, nbbits1);
                    //cout << ' ' ;
                    last.erase(it);
                }
            } else {
                addId(id, (*it).i, nbbits1);
                //cout << ' ' ;
                last.erase(it);
            }
            last.insert({c[i], pos[c[i]][0]});
            pos[c[i]].pop_front();
        }
    }
}

void ComputeAdvice(int *C, int n2, int k2, int m2) {
    n1 = n2;
    k1 = k2;
    m1 = m2;
    v[0].push_back(0);
    v[1].push_back(1);

    nbbits1 = (int)ceil(log2(n1));
    //cout << "BITS " << nbbits1 << '\n';
    for(int i = 0; i < n1; i++)
        c[i] = C[i];
    compute(0);
    //cout << '\n';
    //compute(1);
    //if(v[0].size() < v[1].size()) {
        //cout << "0\n\n";
        for(int i : v[0]) {
            WriteAdvice(i);
        }
    /*} else {
        //cout << "1\n\n";
        for(int i : v[1]) {
            WriteAdvice(i);
        }
    }*/
}

#include "assistant.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

bool fin[N], in[N];
int n, k, len, nbbits, id = 1, b[N];

int read() {
    int val = 0;
    for(int i = 0; i < nbbits; i++) {
        val = val * 2 + b[id];
        //cout << b[id] << ' ';
        id++;
    }
    /*cout << '\n';
    cout << "READ " << val << '\n';*/
    return val;
}

void traite() {
    for(int i = 0; i < n; i++) {
        int j = GetRequest();
        if(!in[j]) {
            in[j] = true;
            int a = read();
            in[a] = false;
            PutBack(a);
        }
    }
}

void traiteSaute() {
    vector<int> suppr;
    for(int i = 0; i < k; i++) {
        if(b[id] == 1) {
            suppr.push_back(i);
        }
        id++;
    }
    for(int i = 0; i < n; i++) {
        int j = GetRequest(),
            t = b[id];
        id++;

        if(!in[j]) {
            in[j] = true;
            if(suppr.empty()) {
                int a = read();
                in[a] = false;
                PutBack(a);
            } else {
                int a = suppr.back();
                in[a] = false;
                PutBack(suppr.back());
                suppr.pop_back();
            }
        }

        if(t == 1)
            suppr.push_back(j);
    }
}

void Assist(unsigned char *A, int n1, int k1, int r1) {
    for(int i = 0; i < k1; i++)
        in[i] = true;
    /*for(int i = 0; i < r1; i++)
        cout << (int)A[i];
    cout << '\n';*/
    n = n1;
    k = k1;
    len = r1;
    for(int i = 0; i < len; i++)
        if((A[i] == 1))
            b[i] = 1;
        else
            b[i] = 0;
    nbbits = (int)ceil(log2(n));
    //cout << "BITS " << nbbits << '\n';
    if(A[0] == '0') {
        traite();
    } else {
        traiteSaute();
    }
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 67732 KB Output is correct
2 Incorrect 60 ms 68004 KB Error - Putting back a color that is not on the scaffold
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 81 ms 69216 KB Error - Putting back a color that is not on the scaffold
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 269 ms 79480 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 68004 KB Error - advice is too long
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Runtime error 327 ms 82312 KB Execution killed with signal 11
2 Runtime error 317 ms 82108 KB Execution killed with signal 11
3 Runtime error 324 ms 81868 KB Execution killed with signal 11
4 Runtime error 352 ms 81868 KB Execution killed with signal 11
5 Runtime error 315 ms 82148 KB Execution killed with signal 11
6 Runtime error 320 ms 81916 KB Execution killed with signal 11
7 Runtime error 324 ms 81844 KB Execution killed with signal 11
8 Runtime error 318 ms 81924 KB Execution killed with signal 11
9 Runtime error 348 ms 81908 KB Execution killed with signal 11
10 Runtime error 451 ms 87196 KB Execution killed with signal 11