oj.uz

Submission #928044

# Submission time Handle Problem Language Result Execution time Memory
928044 2024-02-15T19:00:10 Z definitelynotmee Last supper (IOI12_supper) C++17
100 / 100
 95 ms 7672 KB 
#include "advisor.h"
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
#define O_O
using namespace std;
template <typename T>
using bstring = basic_string<T>;
template <typename T>
using matrix = vector<vector<T>>;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef double dbl;
typedef long double dbll;
const ll INFL = 4e18+25;
const int INF = 1e9+42;
const double EPS = 1e-7;
const int MOD = 998244353;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
const int MAXN = 1e6+1;

void ComputeAdvice(int *C, int N, int K, int M) {
    
    K = min(K,N);
    vector<int> advice(N+K,1);

    vector<int> last(N,-1);
    iota(last.begin(), last.begin()+K,0);

    vector<int> next(N+K,INF);

    for(int i = 0; i < N; i++){
        if(last[C[i]] != -1)
            next[last[C[i]]] = i+K;
        last[C[i]] = i+K;
    }

    last = vector<int>(N,-1);
    iota(last.begin(), last.begin()+K,0);

    set<pii, greater<pii>> scaff;

    for(int i = 0; i < K; i++){
        scaff.insert({next[i], i});
    }

    auto pop =[&](){
        pii cur = *scaff.begin();
        scaff.erase(scaff.begin());
        advice[cur.ss] = 0;
    };

    for(int i = 0; i < N; i++){
        if(last[C[i]] != -1 && scaff.count({i+K, last[C[i]]})){
            scaff.erase({i+K, last[C[i]]});
        } else {
            pop();
        }
        scaff.insert({next[i+K], i+K});
        last[C[i]] = i+K;
    }

    for(int i : advice)
        WriteAdvice(i);

}

#include "assistant.h"
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define ff first
#define ss second
#define O_O
using namespace std;
template <typename T>
using bstring = basic_string<T>;
template <typename T>
using matrix = vector<vector<T>>;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef double dbl;
typedef long double dbll;
const ll INFL = 4e18+25;
const int INF = 1e9+42;
const double EPS = 1e-7;
const int MOD = 998244353;
const int RANDOM = chrono::high_resolution_clock::now().time_since_epoch().count();
const int MAXN = 1e6+1;


void Assist(unsigned char *A, int N, int K, int R) {
    vector<int> todelete;

    for(int i = 0; i < K; i++)
        if(A[i] == 0)
            todelete.push_back(i);
    
    set<int> scaff;

    for(int i = 0; i < K; i++)
        scaff.insert(i);
    
    for(int i = 0; i < N; i++){
        int cur = GetRequest();
        if(!scaff.count(cur)){
            
            scaff.insert(cur);
            
            scaff.erase(todelete.back());
            PutBack(todelete.back());
            todelete.pop_back();
        }
        if(A[i+K] == 0)
            todelete.push_back(cur);//, cerr << cur << " todelete" << endl;
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 792 KB Output is correct
2 Correct 0 ms 780 KB Output is correct
3 Correct 1 ms 796 KB Output is correct
4 Correct 2 ms 796 KB Output is correct
5 Correct 2 ms 816 KB Output is correct
6 Correct 4 ms 824 KB Output is correct
7 Correct 3 ms 828 KB Output is correct
8 Correct 5 ms 1072 KB Output is correct
9 Correct 4 ms 820 KB Output is correct
10 Correct 5 ms 1580 KB Output is correct
11 Correct 5 ms 1084 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1116 KB Output is correct
2 Correct 34 ms 2864 KB Output is correct
3 Correct 93 ms 7672 KB Output is correct
4 Correct 51 ms 4384 KB Output is correct
5 Correct 57 ms 4160 KB Output is correct
6 Correct 71 ms 4536 KB Output is correct
7 Correct 82 ms 6156 KB Output is correct
8 Correct 73 ms 5836 KB Output is correct
9 Correct 47 ms 4376 KB Output is correct
10 Correct 95 ms 7432 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 5060 KB Output is correct
2 Correct 86 ms 6748 KB Output is correct
3 Correct 87 ms 6692 KB Output is correct
4 Correct 87 ms 6880 KB Output is correct
5 Correct 80 ms 6060 KB Output is correct
6 Correct 94 ms 6800 KB Output is correct
7 Correct 90 ms 6516 KB Output is correct
8 Correct 84 ms 6668 KB Output is correct
9 Correct 73 ms 6648 KB Output is correct
10 Correct 92 ms 6724 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 816 KB Output is correct
2 Correct 4 ms 1068 KB Output is correct
3 Correct 3 ms 816 KB Output is correct
4 Correct 2 ms 820 KB Output is correct
5 Correct 3 ms 820 KB Output is correct
6 Correct 3 ms 824 KB Output is correct
7 Correct 4 ms 820 KB Output is correct
8 Correct 4 ms 1068 KB Output is correct
9 Correct 4 ms 1080 KB Output is correct
10 Correct 5 ms 1336 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 5752 KB Output is correct - 120000 bits used
2 Correct 89 ms 6000 KB Output is correct - 122000 bits used
3 Correct 87 ms 6364 KB Output is correct - 125000 bits used
4 Correct 87 ms 6268 KB Output is correct - 125000 bits used
5 Correct 86 ms 6272 KB Output is correct - 125000 bits used
6 Correct 86 ms 6348 KB Output is correct - 125000 bits used
7 Correct 86 ms 6628 KB Output is correct - 124828 bits used
8 Correct 87 ms 6376 KB Output is correct - 124910 bits used
9 Correct 87 ms 6264 KB Output is correct - 125000 bits used
10 Correct 81 ms 6268 KB Output is correct - 125000 bits used