oj.uz

Submission #591992

# Submission time Handle Problem Language Result Execution time Memory
591992 2022-07-08T10:55:35 Z cheissmart Last supper (IOI12_supper) C++14
100 / 100
 180 ms 9668 KB 
#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
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 KB Output is correct
2 Correct 0 ms 512 KB Output is correct
3 Correct 3 ms 732 KB Output is correct
4 Correct 3 ms 676 KB Output is correct
5 Correct 3 ms 692 KB Output is correct
6 Correct 5 ms 700 KB Output is correct
7 Correct 5 ms 956 KB Output is correct
8 Correct 5 ms 952 KB Output is correct
9 Correct 6 ms 948 KB Output is correct
10 Correct 8 ms 1080 KB Output is correct
11 Correct 6 ms 948 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1276 KB Output is correct
2 Correct 63 ms 3044 KB Output is correct
3 Correct 160 ms 9668 KB Output is correct
4 Correct 69 ms 4384 KB Output is correct
5 Correct 85 ms 4464 KB Output is correct
6 Correct 110 ms 5224 KB Output is correct
7 Correct 145 ms 7236 KB Output is correct
8 Correct 113 ms 7272 KB Output is correct
9 Correct 63 ms 4448 KB Output is correct
10 Correct 161 ms 8796 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 119 ms 6416 KB Output is correct
2 Correct 152 ms 7856 KB Output is correct
3 Correct 180 ms 8008 KB Output is correct
4 Correct 161 ms 8200 KB Output is correct
5 Correct 144 ms 7200 KB Output is correct
6 Correct 154 ms 8040 KB Output is correct
7 Correct 155 ms 8120 KB Output is correct
8 Correct 137 ms 8224 KB Output is correct
9 Correct 139 ms 7988 KB Output is correct
10 Correct 150 ms 8032 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 932 KB Output is correct
2 Correct 5 ms 948 KB Output is correct
3 Correct 7 ms 784 KB Output is correct
4 Correct 4 ms 688 KB Output is correct
5 Correct 5 ms 820 KB Output is correct
6 Correct 5 ms 900 KB Output is correct
7 Correct 6 ms 960 KB Output is correct
8 Correct 6 ms 964 KB Output is correct
9 Correct 7 ms 956 KB Output is correct
10 Correct 8 ms 1384 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 7296 KB Output is correct - 120000 bits used
2 Correct 155 ms 7612 KB Output is correct - 122000 bits used
3 Correct 165 ms 7968 KB Output is correct - 125000 bits used
4 Correct 176 ms 7972 KB Output is correct - 125000 bits used
5 Correct 153 ms 8108 KB Output is correct - 125000 bits used
6 Correct 158 ms 8028 KB Output is correct - 125000 bits used
7 Correct 158 ms 8200 KB Output is correct - 124828 bits used
8 Correct 151 ms 8036 KB Output is correct - 124910 bits used
9 Correct 157 ms 8056 KB Output is correct - 125000 bits used
10 Correct 139 ms 8020 KB Output is correct - 125000 bits used