oj.uz

Submission #288178

# Submission time Handle Problem Language Result Execution time Memory
288178 2020-09-01T09:35:29 Z erd1 Last supper (IOI12_supper) C++14
43 / 100
 521 ms 17392 KB 
#include "advisor.h"

#include<bits/stdc++.h>
using namespace std;

#include<bits/extc++.h>
using namespace __gnu_pbds;
template<typename T>
using order_statistics_tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

//#define int lld
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define pb push_back
typedef int64_t lld;
typedef pair<int, int> pii;
typedef long double ld;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2> p){
  return out << "(" << p.ff << ", " << p.ss << ")";
}

template<typename Iter>
ostream& outIt(ostream& out, Iter b, Iter e){
  for(Iter i = b; i != e; i++)
    out << (i==b?"":" ") << *i;
  return out;
}

template<typename T>
ostream& operator<<(ostream& out, vector<T> v){
  return outIt(out << '[', all(v)) << ']';
}


template<typename T1, typename T2>
ostream& operator<<(ostream& out, map<T1, T2> m){
  return outIt(out << '{', all(m)) << '}';
}

/*
template<typename T>
using min_heap = priority_queue<T, vector<T>, greater<T>>;
*/

template<typename T1, typename T2>
pair<T1, T2>& operator+=(pair<T1, T2>& a, pair<T1, T2> p){
  return a.ff += p.ff, a.ss += p.ss, a;
}

set<pii> cols;
vector<int> nexts, cn, adv;
order_statistics_tree<int> cols_ord;
void ComputeAdvice(int *C, int N, int K, int M) {
  cn.resize(N, INT_MAX); nexts.resize(N); //adv.resize(N);
  for(int i = N-1; i >= 0; i--){
    nexts[i] = cn[C[i]];
    cn[C[i]] = i;
  }
  //cout << nexts << cn << endl;
  for(int i = 0; i < K; i++)cols.insert({cn[i], i}), cols_ord.insert(i);
  for(int i = 0; i < N; i++){
    //cout << i << endl;
    if(cols_ord.find(C[i]) == cols_ord.end()){
      auto take_out = *prev(cols.end());
      //cout << "oops" << take_out << endl;
      adv.pb((int)cols_ord.order_of_key(take_out.ss));
      cols_ord.erase(take_out.ss);
      cols.erase(take_out);
      cols_ord.insert(C[i]);
    }else{
      cols.erase({cn[C[i]], C[i]});
    }
    cn[C[i]] = nexts[i];
    cols.insert({cn[C[i]], C[i]});
  }
  int bitlen = __lg(K-1)+1;
  //cout << adv << endl;
  for(auto i: adv){
    for(int j = 1; j < K; j <<=1)
      WriteAdvice((i&j)?1:0);
  }
}

#include "assistant.h"

#include<bits/stdc++.h>
using namespace std;

#include<bits/extc++.h>
using namespace __gnu_pbds;
template<typename T>
using order_statistics_tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

//#define int lld
#define ff first
#define ss second
#define all(x) (x).begin(), (x).end()
#define pb push_back
typedef int64_t lld;
typedef pair<int, int> pii;
typedef long double ld;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, pair<T1, T2> p){
  return out << "(" << p.ff << ", " << p.ss << ")";
}

template<typename Iter>
ostream& outIt(ostream& out, Iter b, Iter e){
  for(Iter i = b; i != e; i++)
    out << (i==b?"":" ") << *i;
  return out;
}

template<typename T>
ostream& operator<<(ostream& out, vector<T> v){
  return outIt(out << '[', all(v)) << ']';
}


template<typename T1, typename T2>
ostream& operator<<(ostream& out, map<T1, T2> m){
  return outIt(out << '{', all(m)) << '}';
}

//template<typename T>
//using min_heap = priority_queue<T, vector<T>, greater<T>>;

template<typename T1, typename T2>
pair<T1, T2>& operator+=(pair<T1, T2>& a, pair<T1, T2> p){
  return a.ff += p.ff, a.ss += p.ss, a;
}



/*
void ComputeAdvice(int *C, int N, int K, int M) {
  cn.resize(N, INT_MAX); nexts.resize(N); //adv.resize(N);
  for(int i = N-1; i >= 0; i--){
    nexts[i] = cn[C[i]];
    cn[C[i]] = i;
  }
  //cout << nexts << cn << endl;
  for(int i = 0; i < K; i++)cols.insert({cn[i], i}), cols_ord.insert(i);
  for(int i = 0; i < N; i++){
    //cout << i << endl;
    if(cols_ord.find(C[i]) == cols_ord.end()){
      auto take_out = *prev(cols.end());
      //cout << "oops" << take_out << endl;
      adv.pb((int)cols_ord.order_of_key(take_out.ss));
      cols_ord.erase(take_out.ss);
      cols.erase(take_out);
      cols_ord.insert(C[i]);
    }else{
      cols.erase({cn[C[i]], C[i]});
    }
    cn[C[i]] = nexts[i];
    cols.insert({cn[C[i]], C[i]});
  }
  int bitlen = __lg(K-1)+1;
  for(auto i: adv){
    for(int j = 1; j < K; j <<=1)
      WriteAdvice(i&j);
  }
}
*/

vector<int> tadv;
order_statistics_tree<int> tcols_ord;

void Assist(unsigned char *A, int N, int K, int R) {
  int bitlen = __lg(K)+1;
  tadv.resize(N);
  for(int i = 0, k = 0; i < R; k++)
    for(int j = 1; j < K; j<<=1, i++)
      tadv[k] += j*A[i];
  //cout << tadv << endl;
  for(int i = 0; i < K; i++)tcols_ord.insert(i);
  for (int i = 0, j = 0, x; i < N; i++) {
    int req = GetRequest();
    if(tcols_ord.find(req) == tcols_ord.end())
      x = *tcols_ord.find_by_order(tadv[j++]), PutBack(x), tcols_ord.erase(x), tcols_ord.insert(req);
  }
}

Compilation message

advisor.cpp: In function 'void ComputeAdvice(int*, int, int, int)':
advisor.cpp:80:7: warning: unused variable 'bitlen' [-Wunused-variable]
   80 |   int bitlen = __lg(K-1)+1;
      |       ^~~~~~

assistant.cpp: In function 'void Assist(unsigned char*, int, int, int)':
assistant.cpp:90:7: warning: unused variable 'bitlen' [-Wunused-variable]
   90 |   int bitlen = __lg(K)+1;
      |       ^~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 776 KB Output is correct
2 Correct 1 ms 900 KB Output is correct
3 Correct 2 ms 900 KB Output is correct
4 Correct 5 ms 1096 KB Output is correct
5 Correct 3 ms 1184 KB Output is correct
6 Correct 13 ms 1024 KB Output is correct
7 Correct 6 ms 1184 KB Output is correct
8 Correct 16 ms 1412 KB Output is correct
9 Correct 19 ms 1280 KB Output is correct
10 Correct 13 ms 1280 KB Output is correct
11 Correct 14 ms 1280 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 1792 KB Output is correct
2 Correct 135 ms 5368 KB Output is correct
3 Correct 483 ms 17392 KB Output is correct
4 Correct 239 ms 9952 KB Output is correct
5 Correct 340 ms 11744 KB Output is correct
6 Correct 385 ms 12760 KB Output is correct
7 Correct 385 ms 14312 KB Output is correct
8 Correct 433 ms 15592 KB Output is correct
9 Correct 188 ms 8432 KB Output is correct
10 Correct 384 ms 15600 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 301 ms 10984 KB Output is correct
2 Correct 390 ms 13544 KB Output is correct
3 Correct 385 ms 13808 KB Output is correct
4 Correct 370 ms 13592 KB Output is correct
5 Correct 289 ms 11248 KB Output is correct
6 Correct 377 ms 13928 KB Output is correct
7 Correct 375 ms 13624 KB Output is correct
8 Correct 521 ms 17192 KB Output is correct
9 Correct 267 ms 11648 KB Output is correct
10 Correct 380 ms 13808 KB Output is correct

Subtask #4
0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 1116 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 414 ms 13288 KB Output is partially correct - 772365 bits used
2 Correct 391 ms 13552 KB Output is partially correct - 742095 bits used
3 Correct 414 ms 13808 KB Output is partially correct - 712470 bits used
4 Correct 380 ms 14080 KB Output is partially correct - 712005 bits used
5 Correct 395 ms 13808 KB Output is partially correct - 710610 bits used
6 Correct 391 ms 13648 KB Output is partially correct - 712155 bits used
7 Correct 379 ms 13816 KB Output is partially correct - 711090 bits used
8 Correct 394 ms 13808 KB Output is partially correct - 713340 bits used
9 Correct 390 ms 13808 KB Output is partially correct - 712830 bits used
10 Correct 476 ms 16624 KB Output is partially correct - 1117620 bits used