oj.uz

Submission #698559

# Submission time Handle Problem Language Result Execution time Memory
698559 2023-02-13T19:31:29 Z Half Last supper (IOI12_supper) C++17
0 / 100
 380 ms 18700 KB 
#include "advisor.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"WAFFLES "<<i<<"<\n"
#define INF 1000000000000000000LL
#define EPS (0.00000000001L)
#define pi (3.141592653589793L)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}

template<class A=ll>
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

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

  ll bits = 0;
  while((1<<bits) <= k)
    ++bits;
  vector<ll> nxt_ocur(n);
  vector<ll> tmp(n, n);
  vector<vector<ll>> ocur(n);
  for(ll i = n-1; i >= 0; --i){
    nxt_ocur[i] = tmp[C[i]];
    tmp[C[i]] = i;
  }
  for(ll i = 0; i < n; ++i){
    ocur[C[i]].pb(i);
  }
  set<pair<ll,pair<ll, ll>>> sc;
  set<ll> cnt;
  for(ll i = 0; i < k; ++i){
    if(ocur[i].size() != 0)
      sc.insert({-ocur[i][0], {i, i}});
    else
      sc.insert({-n, {i, i}});
    cnt.insert(i);
  }
  vector<ll> adv(n);
  for(ll i = 0; i < n; ++i){
    if(cnt.find(C[i]) != cnt.end()){
      adv[i] = -1;
      auto it = sc.lower_bound({-i, {-1, C[i]}});
      pair<ll, pair<ll, ll>> upd = *it;
      sc.erase(it);
      upd.ff = nxt_ocur[i];
      sc.insert(upd);
      continue;
    }
    pair<ll, pair<ll, ll>> rem = *sc.begin();
    sc.erase(sc.begin());
    cnt.erase(rem.ss.ss);
    adv[i] = rem.ss.ff;
    sc.insert({-nxt_ocur[i], {rem.ss.ff, C[i]}});
    cnt.insert(C[i]);
  }

  for(ll advi : adv){
    for(ll b = 0; b < bits; ++b)
      WriteAdvice(((advi+1) & (1<<b)) != 0);
  }

}

#include "assistant.h"

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define REP(i,a,b) for(ll i=(ll) a; i<(ll) b; i++)
#define pb push_back
#define mp make_pair
#define pl pair<ll,ll>
#define ff first
#define ss second
#define whole(x) x.begin(),x.end()
#define DEBUG(i) cout<<"WAFFLES "<<i<<"<\n"
#define INF 1000000000000000000LL
#define EPS (0.00000000001L)
#define pi (3.141592653589793L)
#define VV(vvvv,NNNN,xxxx); REP(iiiii,0,NNNN) {vvvv.pb(xxxx);}

template<class A=ll>
void Out(vector<A> a) {REP(i,0,a.size()) {cout<<a[i]<<" ";} cout<<endl;}

template<class A=ll>
void In(vector<A> &a, ll N) {A cur; REP(i,0,N) {cin>>cur; a.pb(cur);}} 

void Assist(unsigned char *A, int N, int K, int R) {

  ll bits = 0;
  while((1<<bits) <= K)
    ++bits;

  vector<ll> sc(K);
  for(ll i = 0; i < K; ++i)
    sc[i] = i;
  for (ll i = 0; i < N; i++) {
    int req = GetRequest();
    ll adv = 0;
    for(ll b = 0; b < bits; ++b){
      adv = adv | (A[bits*i + b]<<b);
    }
    adv--;
    if(adv == -1){
      continue;
    }else{
      PutBack(sc[adv]);
      sc[adv] = req;
    }
  }

}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 504 KB Output is correct
2 Incorrect 0 ms 516 KB Output isn't correct - not an optimal way
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 27 ms 2096 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 291 ms 14140 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

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

Subtask #5
0.0 / 39.0

# Verdict Execution time Memory Grader output
1 Incorrect 355 ms 17040 KB Output isn't correct - not an optimal way
2 Incorrect 361 ms 17384 KB Output isn't correct - not an optimal way
3 Incorrect 350 ms 17668 KB Output isn't correct - not an optimal way
4 Incorrect 380 ms 17688 KB Output isn't correct - not an optimal way
5 Incorrect 348 ms 17612 KB Output isn't correct - not an optimal way
6 Incorrect 355 ms 17600 KB Output isn't correct - not an optimal way
7 Incorrect 353 ms 17612 KB Output isn't correct - not an optimal way
8 Incorrect 357 ms 17660 KB Output isn't correct - not an optimal way
9 Incorrect 367 ms 17708 KB Output isn't correct - not an optimal way
10 Correct 340 ms 18700 KB Output is partially correct - 1500000 bits used