oj.uz

Submission #761128

# Submission time Handle Problem Language Result Execution time Memory
761128 2023-06-19T08:38:56 Z fatemetmhr Last supper (IOI12_supper) C++17
100 / 100
 94 ms 15460 KB 
//  ~ Be Name Khoda ~  //

#include <bits/stdc++.h>
#include "advisor.h"
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

static const int maxn5 =  2e5   + 10;

static vector <int> av[maxn5];
static set <pair<int, int>> cur;
static bool mark[maxn5], rem[maxn5];
static int addtime[maxn5];


void ComputeAdvice(int *C, int n, int k, int m){

    for(int i = n - 1; i >= 0; i--)
        av[C[i]].pb(i);
    for(int i = 0; i < k; i++){
        int last = n;
        addtime[i] = i;
        mark[i] = true;
        if(av[i].size())
            last = av[i].back();
        cur.insert({last, i});
    }
    for(int i = 0; i < n; i++){
        av[C[i]].pop_back();
        int last = n;
        addtime[C[i]] = i + k;
        if(av[C[i]].size())
            last = av[C[i]].back();
        if(mark[C[i]]){
            cur.erase({i, C[i]});
            cur.insert({last, C[i]});
            continue;
        }
        auto it = cur.end();
        it--;
        int v = it->se;
        mark[v] = false;
        cur.erase(it);
        cur.insert({last, C[i]});
        rem[addtime[v]] = true;
        mark[C[i]] = true;
        //cout << "for " << i << ' ' << C[i] << ' ' << last << ' ' << v << ' ' << addtime[v] << endl;
    }
    for(int i = 0; i < n + k; i++)
        WriteAdvice(rem[i]);
}

//  ~ Be Name Khoda ~  //

#include "assistant.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")

using namespace std;

typedef long long ll;

#define pb       push_back
#define mp       make_pair
#define all(x)   x.begin(), x.end()
#define fi       first
#define se       second

static const int maxn5 =  2e5   + 10;

static vector <int> av;
static bool mark[maxn5];

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


    int ind = 0;
    fill(mark, mark + k, true);
    for(int i = 0; i < k; i++)
        av.pb(i);

    for(int i = 0; i < n; i++){
        int req = GetRequest();
        av.pb(req);
        if(!mark[req]){
            while(!A[ind])
                ind++;
            //cout << av.size() << ' ' << ind << endl;
            int v = av[ind++];
            PutBack(v);
            mark[v] = false;
        }
        mark[req] = true;
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5256 KB Output is correct
2 Correct 3 ms 5256 KB Output is correct
3 Correct 4 ms 5392 KB Output is correct
4 Correct 4 ms 5556 KB Output is correct
5 Correct 5 ms 5700 KB Output is correct
6 Correct 5 ms 5632 KB Output is correct
7 Correct 6 ms 5568 KB Output is correct
8 Correct 6 ms 5772 KB Output is correct
9 Correct 5 ms 5696 KB Output is correct
10 Correct 7 ms 5828 KB Output is correct
11 Correct 6 ms 5704 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 6156 KB Output is correct
2 Correct 32 ms 8744 KB Output is correct
3 Correct 76 ms 15460 KB Output is correct
4 Correct 48 ms 12444 KB Output is correct
5 Correct 51 ms 12488 KB Output is correct
6 Correct 62 ms 12652 KB Output is correct
7 Correct 77 ms 13404 KB Output is correct
8 Correct 64 ms 13576 KB Output is correct
9 Correct 45 ms 11140 KB Output is correct
10 Correct 76 ms 13892 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 11188 KB Output is correct
2 Correct 75 ms 13600 KB Output is correct
3 Correct 80 ms 13700 KB Output is correct
4 Correct 78 ms 13544 KB Output is correct
5 Correct 74 ms 12716 KB Output is correct
6 Correct 81 ms 13660 KB Output is correct
7 Correct 94 ms 13556 KB Output is correct
8 Correct 65 ms 14768 KB Output is correct
9 Correct 68 ms 12788 KB Output is correct
10 Correct 83 ms 13716 KB Output is correct

Subtask #4
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5668 KB Output is correct
2 Correct 5 ms 5768 KB Output is correct
3 Correct 5 ms 5648 KB Output is correct
4 Correct 5 ms 5696 KB Output is correct
5 Correct 5 ms 5696 KB Output is correct
6 Correct 5 ms 5656 KB Output is correct
7 Correct 6 ms 5696 KB Output is correct
8 Correct 6 ms 5696 KB Output is correct
9 Correct 6 ms 5704 KB Output is correct
10 Correct 7 ms 5932 KB Output is correct

Subtask #5
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 12256 KB Output is correct - 120000 bits used
2 Correct 71 ms 12356 KB Output is correct - 122000 bits used
3 Correct 75 ms 12584 KB Output is correct - 125000 bits used
4 Correct 80 ms 12632 KB Output is correct - 125000 bits used
5 Correct 75 ms 12612 KB Output is correct - 125000 bits used
6 Correct 77 ms 12592 KB Output is correct - 125000 bits used
7 Correct 72 ms 12648 KB Output is correct - 124828 bits used
8 Correct 73 ms 12648 KB Output is correct - 124910 bits used
9 Correct 84 ms 12552 KB Output is correct - 125000 bits used
10 Correct 71 ms 13680 KB Output is correct - 125000 bits used