oj.uz

Submission #430157

# Submission time Handle Problem Language Result Execution time Memory
430157 2021-06-16T11:45:21 Z someone Last supper (IOI12_supper) C++14
0 / 100
 436 ms 88620 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 < n1; i++)
        pos[i].push_back(INF);
    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++) {
        if(!on[c[i]]) {
            on[c[i]] = true;
            auto it = last.end();
            it--;
            /*for(Val v : last)
                cout << v.val << ' ';
            cout << '\n';*/
            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()) {
                    on[(*it).i] = false;
                    addId(id, (*it).i, nbbits1);
                    //cout << ' ' ;
                    last.erase(it);
                }
            } else {
                on[(*it).i] = false;
                addId(id, (*it).i, nbbits1);
                //cout << "suppr " << (*it).i << ' ' << (*it).val << '\n';
                //cout << ' ' ;
                last.erase(it);
            }
            pos[c[i]].pop_front();
            last.insert({c[i], pos[c[i]][0]});
        }
    }
}

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;
            //cout << a << '\n';
            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 67752 KB Output is correct
2 Incorrect 54 ms 67756 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 87 ms 69788 KB Error - GetRequest() must be called N times
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 350 ms 84232 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 59 ms 68028 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 436 ms 88620 KB Execution killed with signal 11
2 Runtime error 419 ms 88312 KB Execution killed with signal 11
3 Runtime error 425 ms 87872 KB Execution killed with signal 11
4 Runtime error 421 ms 87688 KB Execution killed with signal 11
5 Runtime error 405 ms 87624 KB Execution killed with signal 11
6 Runtime error 410 ms 87888 KB Execution killed with signal 11
7 Runtime error 433 ms 87828 KB Execution killed with signal 11
8 Runtime error 410 ms 87628 KB Execution killed with signal 11
9 Runtime error 408 ms 87768 KB Execution killed with signal 11
10 Runtime error 414 ms 88596 KB Execution killed with signal 11