Submission #591992

#	Time	Username	Problem	Language	Result	Execution time	Memory
591992		cheissmart	Last supper (IOI12_supper)	C++14	100 / 100	180 ms	9668 KiB

advisor

#include "advisor.h"
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define IO_OP ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;

void ComputeAdvice(int *a, int n, int k, int m) {
    vi next_occ(n, INF), nxt(n);
    for(int i = n - 1; i >= 0; i--) {
        nxt[i] = next_occ[a[i]];
        next_occ[a[i]] = i;
    }
    set<pi> s;
    set<int> tt;
    for(int i = 0; i < k; i++) {
        s.insert({next_occ[i], i});
        tt.insert(i);
    }
    V<bool> must(n);
    for(int i = 0; i < n; i++) {
        if(tt.find(a[i]) != tt.end()) {
            must[i] = true;
            s.erase({i, a[i]});
            s.insert({nxt[i], a[i]});
        } else {
            must[i] = false;
            auto[pos, val] = *s.rbegin();
            s.erase({pos, val});
            tt.erase(val);

            s.insert({nxt[i], a[i]});
            tt.insert(a[i]);
        }
    }
    V<bool> aux(n), send;
    for(int i = n - 1; i >= 0; i--) {
        send.PB(aux[a[i]]);
        aux[a[i]] = must[i];
    }
    for(int i = k - 1; i >= 0; i--) {
        send.PB(aux[i]);
    }
    reverse(ALL(send));
    for(bool b:send)
        WriteAdvice(b);
}
// WriteAdvice

assistant

#include "assistant.h"
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define IO_OP ios::sync_with_stdio(0), cin.tie(0)
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;

void Assist(unsigned char *a, int n, int k, int r) {
    set<int> must, not_must;
    for(int i = 0; i < k; i++) {
        if(a[i]) must.insert(i);
        else not_must.insert(i);
    }
    for(int i = 0; i < n; i++) {
        int req = GetRequest();
        if(must.count(req)) {
            must.erase(req);
        } else {
            assert(not_must.size());
            PutBack(*not_must.begin());
            not_must.erase(not_must.begin());
        }
        if(a[i + k]) must.insert(req);
        else not_must.insert(req);
    }
}

Compilation message (stderr)

advisor.cpp: In function 'void ComputeAdvice(int*, int, int, int)':
advisor.cpp:43:17: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   43 |             auto[pos, val] = *s.rbegin();
      |                 ^

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 35 / 35
• Subtask 5: 39 / 39