Submission #799456

#	Time	Username	Problem	Language	Result	Execution time	Memory
799456		mosiashvililuka	Parrots (IOI11_parrots)	C++14	100 / 100	1893 ms	59260 KiB

encoder

#include<bits/stdc++.h>
#include "encoder.h"
#include "encoderlib.h"
#define T rieajre
#define a djsiajd
#define b hidah
#define c jeiaj
#define d askdoaojksod
#define e hcjdkafa
#define i hnckhnfisda
#define j djsiajdsa
#define ii cxvcxvkn
#define jj vclkalkf
#define zx asjodoasjd
#define xc mlqwemqlewm
#define f dsmkzfmdkmrqw
#define K qwoeqweoiq
#define ans progprogpro
#define xr mremeraeormaeor
#define pas qwieoqiepsa
#define dp dpsdpsai
#define ZX ajojoejwqoe
#define ADD ADsfdjwoerfjwper
#define MUL dsakldmul
#define comp COmpwapewpqkewqe
using namespace std;
const long long T=1000000000000000000LL;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,f[1009],K;
vector <long long> xr[1009],pas,dp[1009][1009],ZX;
vector <long long> ADD(vector <long long> A, vector <long long> B){
  int i=0;
  long long zx=0;
  vector <long long> ans;
  while(1){
    if(i<A.size()) zx+=A[i];
    if(i<B.size()) zx+=B[i];
    if(zx==0&&i>=max(A.size(),B.size())) break;
    ans.push_back(zx%T);zx/=T;i++;
  }
  return ans;
}
bool comp(vector <long long> A, vector <long long> B){
  if(A.size()<B.size()) return 1;
  if(A.size()>B.size()) return 0;
  int i=0;
  for(i=A.size()-1; i>=0; i--){
    if(A[i]<B[i]) return 1;
    if(A[i]>B[i]) return 0;
  }
  return 1;
}
vector <long long> MUL(vector <long long> v, long long q){
  vector <long long> qw;qw.push_back(0);
  if(q==0) return qw;
  if(q==1) return v;
  qw=MUL(v,q/2);qw=ADD(qw,qw);
  if(q%2==0) return qw; else return ADD(qw,v);
}
void encode(int NN, int MM[])
{
  xr[0].clear();pas.clear();
  a=NN;
  for(i=1; i<=a; i++) f[i]=MM[i-1];
  xr[0].push_back(1);
  for(i=1; i<=a+1; i++){
    xr[i]=MUL(xr[i-1],256);
  }

  pas.push_back(1);
  for(i=1; i<=a; i++){
    if(f[i]!=0) pas=ADD(pas,MUL(xr[i-1],f[i]));
  }

  K=a*5;
  for(i=0; i<=K; i++){
    for(j=0; j<=255; j++){
      dp[i][j].clear();
      if(i!=0) dp[i][j].push_back(0); else dp[i][j].push_back(1);
    }
  }

  for(i=1; i<=K; i++){
    for(j=0; j<=255; j++){
      dp[i][j]=dp[i-1][j];
      if(j!=0) dp[i][j]=ADD(dp[i][j],dp[i][j-1]);
    }
  }

  ZX.clear();ZX.push_back(0);
  for(i=K; i>=1; i--){
    for(j=0; j<=255; j++){
      if(comp(pas,ADD(ZX,dp[i][j]))==1){
        break;
      }
    }
    send(j);
    if(j!=0) ZX=ADD(ZX,dp[i][j-1]);
  }
}

decoder

#include<bits/stdc++.h>
#include "decoder.h"
#include "decoderlib.h"
using namespace std;
const long long T=1000000000000000000LL;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,f[1009],K,ans[1009];
vector <long long> xr[1009],pas,dp[1009][1009],ZX,XC,CV;
vector <long long> ADD(vector <long long> A, vector <long long> B){
  int i=0;
  long long zx=0;
  vector <long long> ans;
  while(1){
    if(i<A.size()) zx+=A[i];
    if(i<B.size()) zx+=B[i];
    if(zx==0&&i>=max(A.size(),B.size())) break;
    ans.push_back(zx%T);zx/=T;i++;
  }
  return ans;
}
bool comp(vector <long long> A, vector <long long> B){
  if(A.size()<B.size()) return 1;
  if(A.size()>B.size()) return 0;
  int i=0;
  for(i=A.size()-1; i>=0; i--){
    if(A[i]<B[i]) return 1;
    if(A[i]>B[i]) return 0;
  }
  return 1;
}
vector <long long> MUL(vector <long long> v, long long q){
  vector <long long> qw;qw.push_back(0);
  if(q==0) return qw;
  if(q==1) return v;
  qw=MUL(v,q/2);qw=ADD(qw,qw);
  if(q%2==0) return qw; else return ADD(qw,v);
}
void decode(int NN, int LL, int XX[])
{
  sort(XX,XX+LL);
  xr[0].clear();pas.clear();
  a=NN;
  xr[0].push_back(1);
  for(i=1; i<=a+1; i++){
    xr[i]=MUL(xr[i-1],256);
  }

  K=a*5;
  for(i=0; i<=K; i++){
    for(j=0; j<=255; j++){
      dp[i][j].clear();
      if(i!=0) dp[i][j].push_back(0); else dp[i][j].push_back(1);
    }
  }

  for(i=1; i<=K; i++){
    for(j=0; j<=255; j++){
      dp[i][j]=dp[i-1][j];
      if(j!=0) dp[i][j]=ADD(dp[i][j],dp[i][j-1]);
    }
  }

  pas.clear();
  pas.push_back(1);
  for(i=LL; i>=1; i--){
    c=XX[i-1];
    if(c!=0) pas=ADD(pas,dp[i][c-1]);
  }

  ZX.clear();ZX.push_back(0);
  for(i=a; i>=1; i--){
    XC.clear();XC.push_back(0);
    for(j=0; j<=255; j++){
      CV=XC;
      XC=ADD(XC,xr[i-1]);
      if(comp(pas,ADD(ZX,XC))==1){
        break;
      }
    }
    ans[i]=j;
    if(j!=0) ZX=ADD(ZX,CV);
  }

  for(i=1; i<=a; i++) output(ans[i]);
}

Compilation message (stderr)

encoder.cpp: In function 'std::vector<long long int> ADsfdjwoerfjwper(std::vector<long long int>, std::vector<long long int>)':
encoder.cpp:35:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     if(i<A.size()) zx+=A[i];
      |         ^
encoder.cpp:36:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     if(i<B.size()) zx+=B[i];
      |         ^
encoder.cpp:37:16: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   37 |     if(zx==0&&i>=max(A.size(),B.size())) break;
      |                ^

decoder.cpp: In function 'std::vector<long long int> ADD(std::vector<long long int>, std::vector<long long int>)':
decoder.cpp:13:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   13 |     if(i<A.size()) zx+=A[i];
      |        ~^~~~~~~~~
decoder.cpp:14:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     if(i<B.size()) zx+=B[i];
      |        ~^~~~~~~~~
decoder.cpp:15:16: warning: comparison of integer expressions of different signedness: 'int' and 'const long unsigned int' [-Wsign-compare]
   15 |     if(zx==0&&i>=max(A.size(),B.size())) break;
      |               ~^~~~~~~~~~~~~~~~~~~~~~~~

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