oj.uz

Submission #698560

# Submission time Handle Problem Language Result Execution time Memory
698560 2023-02-13T19:32:39 Z Half Last supper (IOI12_supper) C++17
34 / 100
 361 ms 20832 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
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 516 KB Output is correct
2 Correct 1 ms 508 KB Output is correct
3 Correct 3 ms 748 KB Output is correct
4 Correct 4 ms 904 KB Output is correct
5 Correct 4 ms 948 KB Output is correct
6 Correct 11 ms 1312 KB Output is correct
7 Correct 11 ms 1372 KB Output is correct
8 Correct 12 ms 1560 KB Output is correct
9 Correct 12 ms 1400 KB Output is correct
10 Correct 13 ms 1648 KB Output is correct
11 Correct 15 ms 1572 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 2068 KB Output is correct
2 Correct 137 ms 7828 KB Output is correct
3 Correct 361 ms 20832 KB Output is correct
4 Correct 158 ms 12400 KB Output is correct
5 Correct 230 ms 13980 KB Output is correct
6 Correct 299 ms 15700 KB Output is correct
7 Correct 343 ms 18152 KB Output is correct
8 Correct 287 ms 17352 KB Output is correct
9 Correct 111 ms 10556 KB Output is correct
10 Correct 356 ms 19360 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 285 ms 14144 KB Output is correct
2 Correct 349 ms 18776 KB Output is correct
3 Correct 351 ms 18820 KB Output is correct
4 Correct 345 ms 18640 KB Output is correct
5 Correct 357 ms 17808 KB Output is correct
6 Correct 347 ms 18860 KB Output is correct
7 Correct 346 ms 18812 KB Output is correct
8 Correct 331 ms 19768 KB Output is correct
9 Correct 332 ms 17944 KB Output is correct
10 Correct 346 ms 18796 KB Output is correct

Subtask #4
0 / 35.0

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

Subtask #5
8.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 359 ms 17160 KB Output is partially correct - 1500000 bits used
2 Correct 347 ms 17348 KB Output is partially correct - 1500000 bits used
3 Correct 351 ms 17660 KB Output is partially correct - 1500000 bits used
4 Correct 353 ms 17704 KB Output is partially correct - 1500000 bits used
5 Correct 349 ms 17668 KB Output is partially correct - 1500000 bits used
6 Correct 349 ms 17764 KB Output is partially correct - 1500000 bits used
7 Correct 353 ms 17584 KB Output is partially correct - 1497585 bits used
8 Correct 353 ms 17720 KB Output is partially correct - 1500000 bits used
9 Correct 347 ms 17664 KB Output is partially correct - 1500000 bits used
10 Correct 336 ms 18624 KB Output is partially correct - 1500000 bits used