oj.uz

Submission #698558

# Submission time Handle Problem Language Result Execution time Memory
698558 2023-02-13T19:16:56 Z Half Last supper (IOI12_supper) C++17
0 / 100
 364 ms 19256 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;
      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){
    if(advi == -1){
      for(ll b = 0; b < bits; ++b)
        WriteAdvice(0);
    }else{
      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(N);
  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);
    }
    if(adv == 0){
      continue;
    }else{
      adv--;
      PutBack(sc[adv]);
      sc[adv] = req;
    }
  }

}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 508 KB Output is correct
2 Incorrect 1 ms 512 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 2204 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 271 ms 14664 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 2 ms 900 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 349 ms 17756 KB Output isn't correct - not an optimal way
2 Incorrect 364 ms 17936 KB Output isn't correct - not an optimal way
3 Incorrect 338 ms 18132 KB Output isn't correct - not an optimal way
4 Incorrect 356 ms 18228 KB Output isn't correct - not an optimal way
5 Incorrect 354 ms 18244 KB Output isn't correct - not an optimal way
6 Incorrect 345 ms 18248 KB Output isn't correct - not an optimal way
7 Incorrect 348 ms 18324 KB Output isn't correct - not an optimal way
8 Incorrect 339 ms 18264 KB Output isn't correct - not an optimal way
9 Incorrect 343 ms 18232 KB Output isn't correct - not an optimal way
10 Correct 334 ms 19256 KB Output is partially correct - 1500000 bits used