oj.uz

답안 #114863

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
114863 2019-06-03T15:32:33 Z KLPP 앵무새 (IOI11_parrots) C++14
100 / 100
 1653 ms 46544 KB 
#include "encoder.h"
#include "encoderlib.h"
#include<bits/stdc++.h>
using namespace std;
#define sz 72
#define rep(i,a,b) for(int i=a;i<b;i++)
struct Bignum{
  int arr[sz];
};
Bignum sum(Bignum A,Bignum B){
  Bignum result;
  int carry=0;
  rep(i,0,sz){
    result.arr[i]=(A.arr[i]+B.arr[i]+carry);
    carry=result.arr[i]/256;
    result.arr[i]%=256;
  }
  return result;
}
bool Bigger(Bignum A, Bignum B){
  for(int i=sz-1;i>-1;i--){
    if(A.arr[i]>B.arr[i])return true;
    if(A.arr[i]<B.arr[i])return false;
  }
  return true;
}
Bignum difference(Bignum A, Bignum B){
  Bignum result;
  int carry=0;
  rep(i,0,sz){
    result.arr[i]=A.arr[i]-B.arr[i]-carry;
    if(result.arr[i]<0){
      result.arr[i]+=256;
      carry=1;
    }else{
      carry=0;
    }
  }
  return result;
}
void print(Bignum A){
  for(int i=sz-1;i>-1;i--){
    cout<<A.arr[i]<<" ";
  }cout<<endl;
}
bool visited[400][256];
Bignum table[400][256];
void comb(int a, int b){
  //cout<<a<<" "<<b<<endl;
  if(visited[a][b])return;
  
  if(a>0 && b>0){
    comb(a,b-1);
    comb(a-1,b);
    table[a][b]=sum(table[a-1][b],table[a][b-1]);
    
  }
  else table[a][b]=table[0][0];
  visited[a][b]=true;
}
void encode(int N, int M[])
{
  int n=N;
  //n=64;
  rep(i,0,5*n+5){
    rep(j,0,256)visited[i][j]=false;
  }
  visited[0][0]=true;
  rep(i,0,sz)table[0][0].arr[i]=0;
  table[0][0].arr[0]=1;
  int floor=(9*n)/2;
  //cout<<floor<<endl;
  //comb(5*n,255);
  //print(table[floor][255]);
  Bignum target;
  rep(i,0,sz)target.arr[i]=0;
  rep(i,0,n)target.arr[i]=M[i];
  //target=sum(target,table[0][0]);
  for(int i=5*n-1;i>-1;i--){
    /*int hi=-1;
    rep(j,0,255){
      if(!Bigger(target,table[i+1][j])){
	hi=j;
	j=256;
      }
      }*/
    int lo=-1;
    int hi=255;
    while(hi-lo>1){
      //cout<<lo<<" "<<hi<<endl;
      int mid=(hi+lo)/2;
      comb(i+1,mid);
      if(!Bigger(target,table[i+1][mid]))hi=mid;
      else lo=mid;
    }
    if(hi>0){
      target=difference(target,table[i+1][hi-1]);
    }
    //cout<<hi<<endl;
    send(hi);
  }
  //comb(6,5);
  //print(table[6][5]);
}
#include "decoder.h"
#include "decoderlib.h"
#include<bits/stdc++.h>
using namespace std;
#define sz 72
#define rep(i,a,b) for(int i=a;i<b;i++)
bool Visited[400][256];

struct Bignum{
  int arr[sz];
};
Bignum Table[400][256];
Bignum Sum(Bignum A,Bignum B){
  Bignum result;
  int carry=0;
  rep(i,0,sz){
    result.arr[i]=(A.arr[i]+B.arr[i]+carry);
    carry=result.arr[i]/256;
    result.arr[i]%=256;
  }
  return result;
}
bool bigger(Bignum A, Bignum B){
  for(int i=sz-1;i>-1;i--){
    if(A.arr[i]>B.arr[i])return true;
    if(A.arr[i]<B.arr[i])return false;
  }
  return false;
}
Bignum Difference(Bignum A, Bignum B){
  Bignum result;
  int carry=0;
  rep(i,0,sz){
    result.arr[i]=A.arr[i]-B.arr[i]-carry;
    if(result.arr[i]<0){
      result.arr[i]+=256;
      carry=1;
    }else{
      carry=0;
    }
  }
  return result;
}

void Comb(int a, int b){
  //cout<<a<<" "<<b<<endl;
  if(Visited[a][b])return;
  
  if(a>0 && b>0){
    Comb(a,b-1);
    Comb(a-1,b);
    Table[a][b]=Sum(Table[a-1][b],Table[a][b-1]);
    
  }
  else Table[a][b]=Table[0][0];
  Visited[a][b]=true;
}
void decode(int N, int L, int X[])
{
  int n=N;
  
  rep(i,0,5*n+5){
    rep(j,0,256)Visited[i][j]=false;
  }
  Visited[0][0]=true;
  rep(i,0,sz)Table[0][0].arr[i]=0;
  Table[0][0].arr[0]=1;
  
  
  sort(X,X+L);
  Bignum target;
  rep(i,0,sz)target.arr[i]=0;
  rep(i,0,L){
    if(X[i]>0){
      Comb(i+1,X[i]-1);
      target=Sum(target,Table[i+1][X[i]-1]);
    }
  }
  rep(i,0,n)output(target.arr[i]);
}

Compilation message

encoder.cpp: In function 'void encode(int, int*)':
encoder.cpp:71:7: warning: unused variable 'floor' [-Wunused-variable]
   int floor=(9*n)/2;
       ^~~~~

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 17 ms 4352 KB Output is correct

Subtask #2
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 5176 KB Output is correct
2 Correct 113 ms 6480 KB Output is correct
3 Correct 158 ms 8088 KB Output is correct
4 Correct 170 ms 8528 KB Output is correct

Subtask #3
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 5184 KB Output is correct
2 Correct 103 ms 6384 KB Output is correct
3 Correct 153 ms 7920 KB Output is correct
4 Correct 166 ms 8512 KB Output is correct

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 5104 KB Output is correct
2 Correct 170 ms 8544 KB Output is correct
3 Correct 222 ms 10224 KB Output is correct
4 Correct 392 ms 14416 KB Output is correct
5 Correct 427 ms 14576 KB Output is correct
6 Correct 422 ms 15344 KB Output is correct

Subtask #5
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 169 ms 8568 KB Output is correct - P = 5.000000
2 Correct 433 ms 15080 KB Output is correct - P = 5.000000
3 Correct 459 ms 15672 KB Output is correct - P = 5.000000
4 Correct 1059 ms 32672 KB Output is correct - P = 5.000000
5 Correct 1507 ms 43792 KB Output is correct - P = 5.000000
6 Correct 1625 ms 45808 KB Output is correct - P = 5.000000
7 Correct 1653 ms 46544 KB Output is correct - P = 5.000000