oj.uz

Submission #925462

# Submission time Handle Problem Language Result Execution time Memory
925462 2024-02-11T16:50:50 Z anton Last supper (IOI12_supper) C++17
60 / 100
 332 ms 23760 KB 
#include<bits/stdc++.h>
using namespace std;


#define pii pair<int, int>
#include "advisor.h"

const int INF = 1e9;
void ComputeAdvice(int *C, int N, int K, int M) {

  vector<int> put_down;
  vector<vector<int>> oc;

  oc.resize(N);
  for(int i = 0; i<N; i++){
    oc[C[i]].push_back(i);
  }

  set<int> zeros;
  set<int> ones;

  for(int i = 0; i<N; i++){
    oc[i].push_back(INF);
    reverse(oc[i].begin(), oc[i].end());
    if(oc[i].size()==1 || (oc[i].size()==2 && i>=K)){
      zeros.insert(i);
    }
  }

  
  
  set<pii> cur_colors;
  for(int i = 0; i<K; i++){
    cur_colors.insert({oc[i].back(), i});
  }

  for(int i = 0; i<N; i++){
    
    int needed = C[i];
    if(cur_colors.find({oc[C[i]].back(), C[i]}) == cur_colors.end()){
      pii removing = *(--cur_colors.end());
      cur_colors.erase(removing);
      if(zeros.find(removing.second) == zeros.end()){
        put_down.push_back(removing.second);
      }
    }
    else{
      cur_colors.erase({oc[needed].back(), needed});
    }
    oc[needed].pop_back();
    cur_colors.insert({oc[needed].back(), needed});

    
  }

  vector<int> nz;
  
  map<int, int> non_zeros;

  for(int i = 0; i<N; i++){
    if(zeros.find(i) == zeros.end()){
      WriteAdvice(1);
      nz.push_back(i);
    }
    else{
      
      WriteAdvice(0);
    }
  }

  sort(nz.begin(), nz.end());
  for(int i = 0; i<nz.size(); i++)non_zeros[nz[i]] = i;

  int log2 = 1;

  while((1<<log2)<nz.size()){
    log2++;
  }
  for(auto e: put_down){
    for(int i = 0; i<log2; i++){
      WriteAdvice((non_zeros[e]&(1<<i))>>i);
    }
  }

}

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


#define pii pair<int, int>

#include "assistant.h"

void Assist(unsigned char *A, int N, int K, int R) {
  set<int> cur_colors;
  for(int i = 0; i<K; i++){
    cur_colors.insert(i);
  }
  vector<int> put_down;
  set<int> zeros;
  vector<int> nz;
  
  map<int, int> non_zeros;
  for(int i = 0; i<N; i++){
    int val =A[i];
    if(val == 0){
      zeros.insert(i);
    }
    else{
      nz.push_back(i);
    }
  }
  sort(nz.begin(), nz.end());

  int log2 = 1;

  while((1<<log2)<nz.size()){
    log2++;
  }

  for(int i =N; i<R; i+=log2){
    int val = 0;
    for(int j = 0; j<log2; j++){
      val += A[j+i] * (1<<j);
    }
    put_down.push_back(nz[val]);
  }

  reverse(put_down.begin(), put_down.end());
  set<int> zeros_inside;

  for(int i = 0; i<K; i++){
    if(zeros.find(i)!=zeros.end()){
      zeros_inside.insert(i);
    }
  }
  for (int i = 0; i < N; i++) {
    int req = GetRequest();
    if(zeros_inside.size()>0 && cur_colors.find(req) == cur_colors.end()){
      //cout<<*zeros_inside.begin()<<endl;
      PutBack(*zeros_inside.begin());
      zeros_inside.erase(zeros_inside.begin());
  
    }
    else if(cur_colors.find(req) == cur_colors.end()){
      //cout<<put_down.back()<<endl;
      PutBack(put_down.back());
      cur_colors.erase(put_down.back());
      put_down.pop_back();
    }


    if(zeros.find(req) != zeros.end()){
      zeros_inside.insert(req);
    }
    else{
      cur_colors.insert(req);
    }
  }

}

Compilation message

advisor.cpp: In function 'void ComputeAdvice(int*, int, int, int)':
advisor.cpp:72:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(int i = 0; i<nz.size(); i++)non_zeros[nz[i]] = i;
      |                  ~^~~~~~~~~~
advisor.cpp:76:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |   while((1<<log2)<nz.size()){
      |         ~~~~~~~~~^~~~~~~~~~

assistant.cpp: In function 'void Assist(unsigned char*, int, int, int)':
assistant.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   while((1<<log2)<nz.size()){
      |         ~~~~~~~~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 780 KB Output is correct
2 Correct 0 ms 792 KB Output is correct
3 Correct 2 ms 788 KB Output is correct
4 Correct 5 ms 1340 KB Output is correct
5 Correct 11 ms 1920 KB Output is correct
6 Correct 10 ms 1652 KB Output is correct
7 Correct 5 ms 1588 KB Output is correct
8 Correct 5 ms 1592 KB Output is correct
9 Correct 12 ms 1908 KB Output is correct
10 Correct 8 ms 1864 KB Output is correct
11 Correct 8 ms 1600 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 2712 KB Output is correct
2 Correct 114 ms 10292 KB Output is correct
3 Correct 200 ms 20316 KB Output is correct
4 Correct 298 ms 20592 KB Output is correct
5 Correct 290 ms 20348 KB Output is correct
6 Correct 267 ms 20180 KB Output is correct
7 Correct 226 ms 19796 KB Output is correct
8 Correct 126 ms 16324 KB Output is correct
9 Correct 332 ms 23760 KB Output is correct
10 Correct 224 ms 20184 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 169 ms 15836 KB Output is correct
2 Correct 229 ms 19828 KB Output is correct
3 Correct 221 ms 20200 KB Output is correct
4 Correct 220 ms 20116 KB Output is correct
5 Correct 208 ms 19400 KB Output is correct
6 Correct 223 ms 20184 KB Output is correct
7 Correct 224 ms 20204 KB Output is correct
8 Correct 154 ms 18892 KB Output is correct
9 Correct 169 ms 20132 KB Output is correct
10 Correct 223 ms 20168 KB Output is correct

Subtask #4
0 / 35.0

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

Subtask #5
34.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 231 ms 19616 KB Output is partially correct - 412160 bits used
2 Correct 221 ms 19688 KB Output is partially correct - 388368 bits used
3 Correct 226 ms 20096 KB Output is partially correct - 375808 bits used
4 Correct 221 ms 19980 KB Output is partially correct - 376800 bits used
5 Correct 238 ms 20204 KB Output is partially correct - 380176 bits used
6 Correct 227 ms 20200 KB Output is partially correct - 378592 bits used
7 Correct 229 ms 20216 KB Output is partially correct - 378207 bits used
8 Correct 223 ms 20204 KB Output is partially correct - 376080 bits used
9 Correct 223 ms 20100 KB Output is partially correct - 378000 bits used
10 Correct 172 ms 18920 KB Output is correct - 128665 bits used