Submission #1180818

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180818		n3rm1n	Last supper (IOI12_supper)	C++20	100 / 100	253 ms	87208 KiB

advisor

#include<bits/stdc++.h>
#include "advisor.h"
using namespace std;
const int maxn = 1e5 + 10;
int last[maxn], bitcnt;
int getlog(int x)
{
 for (int i = 0; i < 20; ++ i)
    {
        int p = (1 << i);
        if(p > x)return i-1;
    }
}
void givebits(int x)
{
    for (int i = 0; i < bitcnt; ++ i)
    {
        if((1 << i) & x)WriteAdvice(1);
        else WriteAdvice(0);
    }
}
map < int, int > mp;
deque < int > as[maxn];
int init[maxn], p[maxn];
vector < int > rem[maxn], used[maxn];
int pt[maxn], ptrem[maxn];
void ComputeAdvice(int *C, int N, int K, int M)
{
    mp.clear();

    int n = N;
    int k = K;
    int m = M;
    bitcnt = getlog(N) + 1;
    for (int i = 0; i < n; ++ i)
        as[C[i]].push_back(i);
    for (int i = 0; i < n; ++ i)
        as[i].push_back(n);

    set < pair < int, int > > q;
    for (int i = 0; i < K; ++ i)
    {
        mp[i] = 1;
        q.insert(make_pair(as[i].front(), i));
    }

    for (int i = 0; i < n; ++ i)
    {
        used[C[i]].push_back(i);
        if(mp[C[i]])
        {
            as[C[i]].pop_front();
            int newlast = as[C[i]].front();
            q.erase(make_pair(i, C[i]));
            q.insert(make_pair(newlast, C[i]));

        }
        else
        {
            pair < int, int > w = *q.rbegin();
            int index = w.second;
            q.erase(w);
            as[C[i]].pop_front();
            rem[index].push_back(i);
            int newlast = as[C[i]].front();
            q.insert(make_pair(newlast, C[i]));
            mp[index] = 0;
            mp[C[i]] = 1;
        }
    }
    for (int i = 0;i < n; ++ i)
    {
        used[i].push_back(n);
        rem[i].push_back(n);

    }

    for (int i = 0; i < k; ++ i)
    {
        if(used[i][0] < rem[i][0])init[i] = 1;
        else init[i] = 0;
    }
    for (int i = 0; i < n; ++ i)
    {
        int value = C[i];
        pt[value] ++;
        while(rem[value][ptrem[value]] <= i)
        {
            ptrem[value] ++;
        }
        if(used[value][pt[value]]< rem[value][ptrem[value]])p[i] = 1;
        else p[i] = 0;
    }

    for (int i = 0; i < k; ++ i)
    {
        WriteAdvice(init[i]);
   // cout << init[i+1] << " ";
    }
   //cout << endl;
    for (int i = 0; i < n; ++ i)
    {
        WriteAdvice(p[i]);
       // cout << p[i] << " ";

    }
//cout << endl;
}

assistant

#include <bits/stdc++.h>
#include "assistant.h"
#define pb push_back
using namespace std;
const int maxnn = 1e5 + 10;
vector < int > g;
int n, bitche;
int getlog2(int x)
{

    for (int i = 0; i < 20; ++ i)
    {
        int p = (1 << i);
        if(p > x)return i-1;
    }
}
int curr_bit = 0;
int get_bits()
{
    int ans = 0;
    for (int i = 0; i < bitche; ++ i)
    {
        if(g[curr_bit])ans = (ans | (1 << i));
        curr_bit ++;
    }
    return ans;
}

void Assist(unsigned char *A, int N, int K, int R)
{
   // cout << R << endl;
    n = N;
    bitche = getlog2(N) + 1;
  for (int i = 0; i < R; ++ i)
  {
      g.pb(A[i]);
      //cout << A[i] << " ";

  }  //cout << endl;
    set < int > passive, active;
    map < int, int > mp;
    int curr_bit = 0;
    for (int i = 0; i < K; ++ i)
    {
        if(!g[curr_bit])passive.insert(i);
        else active.insert(i);
        mp[i] = 1;
        curr_bit ++;
    }
    for (int i = 0; i < N; ++ i)
    {
        int curr = GetRequest();
        int type = g[curr_bit];
       curr_bit ++;
        if(mp[curr])
        {
            passive.erase(curr);
            active.erase(curr);
        }
        else
        {
            assert(passive.size());
            //cout << passive.size() << " is passive.size bef del " << endl;
            int del = *passive.rbegin();
            passive.erase(del);
            PutBack(del);
            mp[del] = 0;
        }

        mp[curr] = 1;
        if(type == 0)passive.insert(curr);
        else active.insert(curr);

    }
}

Compilation message (stderr)

# 1번째 컴파일 단계

advisor.cpp: In function 'int getlog(int)':
advisor.cpp:13:1: warning: control reaches end of non-void function [-Wreturn-type]
   13 | }
      | ^

# 2번째 컴파일 단계

assistant.cpp: In function 'int getlog2(int)':
assistant.cpp:16:1: warning: control reaches end of non-void function [-Wreturn-type]
   16 | }
      | ^

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 35 / 35
• Subtask 5: 39 / 39