oj.uz

Submission #482942

# Submission time Handle Problem Language Result Execution time Memory
482942 2021-10-27T00:17:38 Z hidden1 Last supper (IOI12_supper) C++14
100 / 100
 135 ms 9828 KB 
#include "advisor.h"

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#ifndef LOCAL
#define cerr if(false) cerr
#endif
#define endl "\n"
#define all(x) (x).begin(), (x).end()
#define forn(i, n) for(int i = 0; i < n; i ++)
#define revn(i, n) for(int i = n - 1; i >= 0; i --)
typedef long long ll;
template<class T, template<class T2, class A=allocator<T2> > class cont> inline ostream &operator <<(ostream &out, const cont<T> &x) { for(const auto &it : x) { out << it << " ";} return out;}
template<class T, template<class T2, class A=allocator<T2> > class cont> inline istream &operator >>(istream &in, cont<T> &x) { for(auto &it : x) { in >> it;} return in;}
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;

const int MAX_N = 2e5 + 10;
ll nxt[MAX_N];
ll change[MAX_N];
bool ans[MAX_N];
int n, k, m;
int current[MAX_N];

void ComputeAdvice(int *arr, int n, int k, int m) {
    for(int i = 0; i < n; i ++) {
        nxt[i] = n;
    }
    for(int i = n - 1; i >= 0; i --) {
        change[i] = nxt[arr[i]];
        nxt[arr[i]] = i;
    }
    set<pair<int, int> > st;
    for(int i = 0; i < k; i ++) {
        st.insert({nxt[i], i});
        current[i] = i;
    }
    int cnt = k;

    auto removeMax = [&st]() {
        auto it = st.end();
        it --;
        ans[current[(*it).second]] = 1;
        st.erase(it);
    };

    for(int i = 0; i < n; i ++) {
        if(st.find({i, arr[i]}) != st.end()) {
            auto it = st.find({i, arr[i]});
            ans[current[(*it).second]] = 0;
            st.erase(it);
        } else {
            removeMax();
        }

        nxt[arr[i]] = change[i];
        current[arr[i]] = cnt ++;
        st.insert({nxt[arr[i]], arr[i]});
    }
    for(int i = 0; i < cnt; i ++) {
        WriteAdvice(ans[i]);
    }
}

#include "assistant.h"

#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize ("O3")
//#pragma GCC target ("sse4")
#ifndef LOCAL
#define cerr if(false) cerr
#endif
#define endl "\n"
#define all(x) (x).begin(), (x).end()
#define forn(i, n) for(int i = 0; i < n; i ++)
#define revn(i, n) for(int i = n - 1; i >= 0; i --)
typedef long long ll;
template<class T, template<class T2, class A=allocator<T2> > class cont> inline ostream &operator <<(ostream &out, const cont<T> &x) { for(const auto &it : x) { out << it << " ";} return out;}
template<class T, template<class T2, class A=allocator<T2> > class cont> inline istream &operator >>(istream &in, cont<T> &x) { for(auto &it : x) { in >> it;} return in;}
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;

void Assist(unsigned char *ans, int n, int k, int r) {

    set<int> st;
    set<int> bad;

    for(int i = 0; i < k; i ++) {
        st.insert(i);
        if(ans[i]) {
            bad.insert(i);
        }
    }
    int cnt = k;

    for(int i = 0; i < n; i ++) {
        int now = GetRequest();

        if(st.find(now) != st.end()) {
            st.erase(st.find(now));
        } else {
            auto something = bad.begin();
            PutBack(*something);
            st.erase(*something);
            bad.erase(*something);
        }

        st.insert(now);
        if(ans[cnt]) {
            bad.insert(now);
        }

        cnt ++;
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 500 KB Output is correct
2 Correct 0 ms 500 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 648 KB Output is correct
5 Correct 3 ms 780 KB Output is correct
6 Correct 4 ms 780 KB Output is correct
7 Correct 6 ms 920 KB Output is correct
8 Correct 4 ms 928 KB Output is correct
9 Correct 4 ms 908 KB Output is correct
10 Correct 6 ms 912 KB Output is correct
11 Correct 6 ms 908 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1344 KB Output is correct
2 Correct 49 ms 3472 KB Output is correct
3 Correct 118 ms 9040 KB Output is correct
4 Correct 65 ms 6480 KB Output is correct
5 Correct 75 ms 6460 KB Output is correct
6 Correct 98 ms 7104 KB Output is correct
7 Correct 118 ms 8672 KB Output is correct
8 Correct 79 ms 7936 KB Output is correct
9 Correct 60 ms 6444 KB Output is correct
10 Correct 128 ms 9828 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 6588 KB Output is correct
2 Correct 123 ms 7976 KB Output is correct
3 Correct 124 ms 9412 KB Output is correct
4 Correct 123 ms 9380 KB Output is correct
5 Correct 121 ms 8964 KB Output is correct
6 Correct 122 ms 9268 KB Output is correct
7 Correct 125 ms 9268 KB Output is correct
8 Correct 91 ms 8876 KB Output is correct
9 Correct 112 ms 9804 KB Output is correct
10 Correct 125 ms 9404 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 904 KB Output is correct
2 Correct 4 ms 880 KB Output is correct
3 Correct 4 ms 780 KB Output is correct
4 Correct 4 ms 780 KB Output is correct
5 Correct 4 ms 792 KB Output is correct
6 Correct 4 ms 908 KB Output is correct
7 Correct 6 ms 920 KB Output is correct
8 Correct 6 ms 920 KB Output is correct
9 Correct 6 ms 908 KB Output is correct
10 Correct 7 ms 1172 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 7768 KB Output is correct - 120000 bits used
2 Correct 121 ms 7844 KB Output is correct - 122000 bits used
3 Correct 123 ms 8072 KB Output is correct - 125000 bits used
4 Correct 122 ms 8140 KB Output is correct - 125000 bits used
5 Correct 123 ms 8048 KB Output is correct - 125000 bits used
6 Correct 121 ms 8096 KB Output is correct - 125000 bits used
7 Correct 124 ms 8204 KB Output is correct - 124828 bits used
8 Correct 130 ms 8248 KB Output is correct - 124910 bits used
9 Correct 135 ms 8052 KB Output is correct - 125000 bits used
10 Correct 99 ms 7832 KB Output is correct - 125000 bits used