제출 #1235597

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1235597		caacrugon	앵무새 (IOI11_parrots)	C++20	100 / 100	5 ms	840 KiB

encoder

#include "encoder.h"
#include "encoderlib.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

void encode(int N, int M[]){
  ll dp[32][16];
  for(int i=0;i<32;i++){
    for(int j=0;j<16;j++){
      if(i==0){
        dp[i][j]=j;
      }else if(i==1 && j==0){
        dp[i][0]=1+dp[i-1][15];
      }else if(j==0){
        dp[i][0]=(dp[i-1][0]-dp[i-2][0])+dp[i-1][15];
      } else {
        dp[i][j]=dp[i][j-1]+(dp[i-1][j]-dp[i-1][0]);
      }
    }
  }
  ll num=0,p=0;
  for(int i=0;i<N;i+=4){
    ll n1=i<N? M[i]:0;
    ll n2=i+1<N? M[i+1]:0;
    ll n3=i+2<N? M[i+2]:0;
    ll n4=i+3<N? M[i+3]:0;
    num=n1 | (n2<<8) | (n3<<16) | (n4<<24);
    ll r=0,c=0;
    while(dp[r][c]<=num){
      c++;
      if(c>=16){
        c=0;
        r++;
      }
    }
    c--;
    if(c<0){
      c=15;
      r--;
    }
    num-=dp[r][c];
    send((p<<4) | c);
    r--;
    while(r>=0){
      num+=dp[r][0];
      while(dp[r][c]>num)c--;
      send((p<<4) | c);
      num-=dp[r][c];
      r--;
    }
    p++;
  }
}

decoder

#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>

using namespace std;

#define ll long long

void decode(int N, int L, int X[]){
  ll dp[32][16];
  for(int i=0;i<32;i++){
    for(int j=0;j<16;j++){
      if(i==0){
        dp[i][j]=j;
      }else if(i==1 && j==0){
        dp[i][0]=1+dp[i-1][15];
      }else if(j==0){
        dp[i][0]=(dp[i-1][0]-dp[i-2][0])+dp[i-1][15];
      } else {
        dp[i][j]=dp[i][j-1]+(dp[i-1][j]-dp[i-1][0]);
      }
    }
  }
  vector<vector<ll>> ln(16,vector<ll>(0,0));
  for(int i=0;i<L;i++){
    ln[(X[i]>>4) & 0xf].push_back(X[i] & 0xf);
  }
  ll p=0;
  for(int i=0;i<N;i+=4){
    sort(ln[p].begin(), ln[p].end());
    reverse(ln[p].begin(), ln[p].end());
    ll num=0;
    int r=ln[p].size()-1;
    for(int i=0;i<ln[p].size();i++){
      if(i==0){
        num+=dp[r][ln[p][i]];
      } else {
        num+=dp[r][ln[p][i]]-dp[r][0];
      }
      r--;
    }
    if(i<N) output(num & 0xff);
    if(i+1<N) output((num>>8) & 0xff);
    if(i+2<N) output((num>>16) & 0xff);
    if(i+3<N) output((num>>24) & 0xff);
    p++;
  }
}

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