oj.uz

Submission #328698

# Submission time Handle Problem Language Result Execution time Memory
328698 2020-11-17T17:38:14 Z achibasadzishvili Last supper (IOI12_supper) C++14
43 / 100
 492 ms 24912 KB 
#include "advisor.h"
#include<bits/stdc++.h>
#define ll int
#define f first
#define s second
#define pb push_back
#define mp make_pair
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
int L;
void write(ll x){
    for(int i=0; i<L; i++){
        bool k = (x & 1);
        WriteAdvice(k);
        x /= 2;
    }
}
int AC[200005];
void ComputeAdvice(int *c, int n, int k, int m){
    ordered_set ord;
    set<pair<ll,ll> >st;
    set<pair<ll,ll> >::iterator it;
    set<ll>fr[n + 2];
    for(int i=1; i<=20; i++)
        if((1 << i) > k){
            L = i;
            break;
        }
//    cerr << "L: " <<L << '\n';
    for(int i=0; i<n; i++){
        fr[c[i]].insert(i);
    }
    for(int i=0; i<k; i++){
        AC[i] = 1;
        ord.insert(i);
        if(fr[i].size() == 0)
            st.insert(mp(n + 2 , i));
        else
            st.insert(mp((*fr[i].begin()) , i));
    }
    for(int i=0; i<n; i++){
        ll x = c[i];
        if(AC[x] == 1){
            st.erase(mp((*fr[x].begin()) , x));
            fr[x].erase(fr[x].begin());
            if(fr[x].size() == 0)
                st.insert(mp(n + 2 , x));
            else
                st.insert(mp((*fr[x].begin()) , x));
            continue;
        }
        else {
            fr[x].erase(i);
            it = st.end();
            it--;
            int num = (*it).s;
            AC[num] = 0;
            AC[x] = 1;
            int ind = ord.order_of_key(num);
            write(ind);
            ord.insert(x);
            ord.erase(num);
            st.erase(it);
            if(fr[x].size() == 0)
                st.insert(mp(n + 2 , x));
            else
                st.insert(mp((*fr[x].begin()) , x));
        }
    }
}

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
#define ll int
#define f first
#define s second
#define pb push_back
#include "assistant.h"
using namespace std;
int l = 0,ind = 0,ac[200005];
void Assist(unsigned char *A, int n, int k, int R){
    ordered_set ord;
    for(int i=1; i<=20; i++)
        if((1 << i) > k){
            l = i;
            break;
        }
    for(int i=0; i<k; i++){
        ord.insert(i);
        ac[i] = 1;
    }
    for(int i=0; i<n; i++){
        ll x = GetRequest();
        if(ac[x] == 1)continue;
        else {
            ll d = 1,num = 0;
            for(int j=ind; j<ind+l; j++){
                if(A[j] == 1)num += d;
                d *= 2;
            }
            ind += l;
            ll p = (*ord.find_by_order(num));
        //    cerr << "OE: " << p << '\n';
            PutBack(p);
        //    cerr << "Back: " << p << " " << x << '\n';
            ac[p] = 0;
            ac[x] = 1;
            ord.erase(p);
            ord.insert(x);
        }
    }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 968 KB Output is correct
2 Correct 1 ms 916 KB Output is correct
3 Correct 3 ms 1044 KB Output is correct
4 Correct 6 ms 1188 KB Output is correct
5 Correct 6 ms 1492 KB Output is correct
6 Correct 13 ms 1632 KB Output is correct
7 Correct 7 ms 1452 KB Output is correct
8 Correct 19 ms 1780 KB Output is correct
9 Correct 15 ms 2024 KB Output is correct
10 Correct 12 ms 1924 KB Output is correct
11 Correct 13 ms 1752 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 2564 KB Output is correct
2 Correct 135 ms 9664 KB Output is correct
3 Correct 443 ms 24912 KB Output is correct
4 Correct 248 ms 18000 KB Output is correct
5 Correct 344 ms 19616 KB Output is correct
6 Correct 400 ms 21036 KB Output is correct
7 Correct 391 ms 21752 KB Output is correct
8 Correct 409 ms 21040 KB Output is correct
9 Correct 201 ms 16344 KB Output is correct
10 Correct 381 ms 22344 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 316 ms 17704 KB Output is correct
2 Correct 399 ms 22216 KB Output is correct
3 Correct 385 ms 22152 KB Output is correct
4 Correct 367 ms 21508 KB Output is correct
5 Correct 319 ms 19932 KB Output is correct
6 Correct 405 ms 22196 KB Output is correct
7 Correct 398 ms 21976 KB Output is correct
8 Correct 492 ms 24400 KB Output is correct
9 Correct 253 ms 20376 KB Output is correct
10 Correct 399 ms 22132 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 1472 KB Error - advice is too long
2 Halted 0 ms 0 KB -

Subtask #5
17.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 395 ms 21572 KB Output is partially correct - 772365 bits used
2 Correct 393 ms 21412 KB Output is partially correct - 742095 bits used
3 Correct 415 ms 22028 KB Output is partially correct - 712470 bits used
4 Correct 391 ms 22380 KB Output is partially correct - 712005 bits used
5 Correct 390 ms 22248 KB Output is partially correct - 710610 bits used
6 Correct 390 ms 22576 KB Output is partially correct - 712155 bits used
7 Correct 415 ms 22020 KB Output is partially correct - 711090 bits used
8 Correct 399 ms 22224 KB Output is partially correct - 713340 bits used
9 Correct 389 ms 22056 KB Output is partially correct - 712830 bits used
10 Correct 445 ms 24848 KB Output is partially correct - 1117620 bits used