oj.uz

Submission #799456

# Submission time Handle Problem Language Result Execution time Memory
799456 2023-07-31T14:46:52 Z mosiashvililuka Parrots (IOI11_parrots) C++14
100 / 100
 1893 ms 59260 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
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]);
  }
}

#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

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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 49228 KB Output is correct

Subtask #2
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 49680 KB Output is correct
2 Correct 229 ms 50036 KB Output is correct
3 Correct 280 ms 50344 KB Output is correct
4 Correct 328 ms 50632 KB Output is correct

Subtask #3
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 49620 KB Output is correct
2 Correct 192 ms 49968 KB Output is correct
3 Correct 279 ms 50524 KB Output is correct
4 Correct 290 ms 50540 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 145 ms 49704 KB Output is correct
2 Correct 305 ms 50536 KB Output is correct
3 Correct 379 ms 51032 KB Output is correct
4 Correct 627 ms 52720 KB Output is correct
5 Correct 649 ms 52892 KB Output is correct
6 Correct 692 ms 52980 KB Output is correct

Subtask #5
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 50624 KB Output is correct - P = 5.000000
2 Correct 689 ms 53076 KB Output is correct - P = 5.000000
3 Correct 728 ms 53272 KB Output is correct - P = 5.000000
4 Correct 1216 ms 56156 KB Output is correct - P = 5.000000
5 Correct 1579 ms 58304 KB Output is correct - P = 5.000000
6 Correct 1893 ms 58888 KB Output is correct - P = 5.000000
7 Correct 1822 ms 59260 KB Output is correct - P = 5.000000