Submission #1052570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052570		Piokemon	Parrots (IOI11_parrots)	C++17	100 / 100	4 ms	1644 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
using namespace std;

#include <bits/stdc++.h>
typedef __int128 ll;

void encode(int n, int m[]){
  ll ilosc[42][35];
  //     poz ter
  for (int x=0;x<=40;x++){
    for (int y=0;y<=33;y++)ilosc[x][y]=0;
  }
  ilosc[1][1]=1;
  for (int x=1;x<=40;x++){
    for (int y=1;y<=33;y++){
      ilosc[x][y+1]+=ilosc[x][y];
      ilosc[x+1][y]+=ilosc[x][y];
    }
  }
  vector<int> dupa;
  for (int blok=0;blok*8<n;blok++){
    int dlug=min(8,n-blok*8);
    ll wart=0;
    for (int x=0;x<dlug;x++){
      //cerr << (int)wart << ' ' << (int)wart*256 << ' ' << m[blok*8+x] << '\n';
      if (blok*8+x>=n)wart=wart*256;
      else wart=(wart*256)+(ll)m[blok*8+x];
    }
    
    int nr=0; //rang od blok*32 do blok*32+31;
    for (int x=0;x<dlug*5;x++){
      while (ilosc[dlug*5-x][32-nr]<=wart){
        wart-=ilosc[dlug*5-x][32-nr];
        nr++;
      }
      dupa.push_back(nr+blok*32);
    }
  }
  //for (int x:dupa) cerr << "send " << x << '\n';
  for (int x:dupa)send(x);
}

decoder

#include "decoder.h"
#include "decoderlib.h"
using namespace std;

#include <bits/stdc++.h>
typedef __int128 ll;

void decode(int n, int l, int x[])
{
  ll ilosc[42][35];
  //     poz ter
  for (int z=0;z<=40;z++){
    for (int y=0;y<=33;y++)ilosc[z][y]=0;
  }
  ilosc[1][1]=1;
  for (int z=1;z<=40;z++){
    for (int y=1;y<=32;y++){
      ilosc[z][y+1]+=ilosc[z][y];
      ilosc[z+1][y]+=ilosc[z][y];
    }
  }
  sort(x,x+l);
  vector<int> dupa2;
  for (int blok=0;blok*8<n;blok++){
    int dlug=min(8,n-blok*8);
    // bieremy papugi od blok*40 do blok*40+39
    ll wart=0;
    int nr=0;
    for (int y=0;y<5*dlug;y++){
      x[blok*40+y]-=blok*32;
      while(x[blok*40+y]>nr){
        wart+=ilosc[5*dlug-y][32-nr];
        nr++;
      }
    }
    /*cerr << "odeb ";
    vector<int> tempo;
    ll kop=wart;
    while(kop){
      tempo.push_back(kop%(ll)10);
      kop/=(ll)10;
    }
    for (int y=tempo.size()-1;y>=0;y--) cerr << tempo[y];
    cout << '\n';*/
    vector<int> temp;
    for (int y=0;y<dlug;y++){
      temp.push_back(wart%(ll)256);
      wart/=(ll)256;
    }
    for (int y=dlug-1;y>=0;y--)dupa2.push_back(temp[y]);
  }
  while(dupa2.size()>n)dupa2.pop_back();
  //for (int y:dupa2) cerr << "out " << y << '\n';
  for (int y:dupa2) output(y);
}

Compilation message (stderr)

decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:52:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |   while(dupa2.size()>n)dupa2.pop_back();
      |         ~~~~~~~~~~~~^~

• Subtask 1: 17 / 17
• Subtask 2: 17 / 17
• Subtask 3: 18 / 18
• Subtask 4: 29 / 29
• Subtask 5: 19 / 19