oj.uz

Submission #799452

# Submission time Handle Problem Language Result Execution time Memory
799452 2023-07-31T14:44:30 Z mosiashvililuka Parrots (IOI11_parrots) C++14
100 / 100
 1655 ms 59140 KB 
#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
#define eri lurjica
using namespace std;
int eri;
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);
  //cout<<pas[0]<<" pas[0]\n";
  for(i=K; i>=1; i--){
    for(j=0; j<=255; j++){
      if(comp(pas,ADD(ZX,dp[i][j]))==1){
        break;
      }
    }
    //if(j!=0) cout<<"i:"<<i<<"    "<<ZX[0]<<" "<<dp[i][j-1][0]<<"   "<<j<<"\n";
    send(j);
    if(j!=0) ZX=ADD(ZX,dp[i][j-1]);
  }
}

#include<bits/stdc++.h>
#include "decoder.h"
#include "decoderlib.h"
using namespace std;
int eri;
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[])
{
  /*int i, b;
  for(i=0; i<L; i++) {
    b = X[i];
    output(b);
  }*/

  sort(XX,XX+LL);
  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);
  }

  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];
    //cout<<c<<" i "<<i<<"\n";
    if(c!=0) pas=ADD(pas,dp[i][c-1]);
  }

  //cout<<pas[0]<<"\n";
  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,/*dp[i][j-1]*/CV);
  }

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

Compilation message

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

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 49256 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 49652 KB Output is correct
2 Correct 195 ms 50076 KB Output is correct
3 Correct 267 ms 50372 KB Output is correct
4 Correct 300 ms 50568 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 49584 KB Output is correct
2 Correct 199 ms 49996 KB Output is correct
3 Correct 275 ms 50644 KB Output is correct
4 Correct 289 ms 50532 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 49728 KB Output is correct
2 Correct 290 ms 50504 KB Output is correct
3 Correct 391 ms 51124 KB Output is correct
4 Correct 609 ms 52636 KB Output is correct
5 Correct 644 ms 52952 KB Output is correct
6 Correct 767 ms 52944 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 50692 KB Output is correct - P = 5.000000
2 Correct 677 ms 53060 KB Output is correct - P = 5.000000
3 Correct 685 ms 53280 KB Output is correct - P = 5.000000
4 Correct 1150 ms 56260 KB Output is correct - P = 5.000000
5 Correct 1460 ms 58420 KB Output is correct - P = 5.000000
6 Correct 1655 ms 58952 KB Output is correct - P = 5.000000
7 Correct 1628 ms 59140 KB Output is correct - P = 5.000000