| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 235582 | Coroian_David | 앵무새 (IOI11_parrots) | C++11 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "encoder.h"
#include "encoderlib.h"
#define MAX_N 64
using namespace std;
int n;
void aduna(unsigned char a[], unsigned char b[])
{
int i = 1;
int t = 0;
for(i = 1; i <= max(a[0], b[0]) || t; i ++)
{
a[i] += b[i] + t;
t = 0;
if(a[i] > 9)
{
t = a[i] / 10;
a[i] %= 10;
}
}
a[0] = i - 1;
}
bool cmp(unsigned char a[], unsigned char b[])
{
if(a[0] > b[0])
return 1;
if(a[0] < b[0])
return 0;
for(int i = a[0]; i >= 1; i --)
{
if(a[i] != b[i])
return (a[i] > b[i]);
}
return 1;
}
void copyV(unsigned char a[], unsigned char b[])
{
for(int i = 1; i <= a[0]; i ++)
a[i] = 0;
a[0] = b[0];
for(int i = 1; i <= b[0]; i ++)
a[i] = b[i];
}
void scade(unsigned char a[], unsigned char b[])
{
int t = 0;
for(int i = 1; i <= b[0] || t; i ++)
{
int x = (int)a[i] - (int)t - (int)b[i];
t = 0;
if(x < 0)
{
t = 1;
x += 10;
}
a[i] = x;
}
while(a[0] > 1 && a[a[0]] == 0)
a[0] --;
}
struct nr
{
unsigned char v[200];
void operator +=(nr &x)
{
aduna(v, x.v);
}
void operator -=(nr &x)
{
scade(v, x.v);
}
void operator =(nr &x)
{
copyV(v, x.v);
}
bool operator >= (nr &x)
{
return cmp(v, x.v);
}
};
nr dp[255 + 1][MAX_N * 5 + 1];
nr sdp[255 + 1][MAX_N * 5 + 1];
nr mdp[255 + 1][MAX_N * 5 + 1];
nr p2;
nr cod;
nr s;
int done;
void getDp()
{
if(done == 1)
return;
done = 1;
dp[0][0].v[0] = 1;
dp[0][0].v[1] = 1;
sdp[0][0].v[0] = 1;
sdp[0][0].v[1] = 1;
// cout << n << "\n";
int nn = 64;
for(int i = 0; i < 255; i ++)
{
for(int j = 0; j <= nn * 5; j ++)
{
// if(i >= 150)
//cout << i << " " << j << " " << n << "\n";
if(j > 0)
{
sdp[i][j] += sdp[i][j - 1];
mdp[i][j] += mdp[i][j - 1];
}
dp[i][j] = sdp[i][j];
dp[i][j] -= mdp[i][j];
if(n == 0)
cout << dp[i][j].v[0] << " " << dp[i][j].v[1] << " " << dp[i][j].v[2] << "\n";
if(dp[i][j].v[0] != 0)
{
sdp[i + 1][j] += dp[i][j];
if(j + 256 <= nn * 5)
mdp[i + 1][j + 256] += dp[i][j];
}
}
}
}
void afis(nr a)
{
for(int i = a.v[0]; i >= 1; i --)
cout << (int)a.v[i];
cout << "\n";
}
void encode(int N, int M[])
{
n = N;
getDp();
int k = 0;
int a[700];
for(int i = 0; i < N; i ++)
{
for(int j = 7; j >= 0; j --)
a[++ k] = (((1 << j) & M[i]) != 0);
}
memset(p2.v, 0, sizeof(p2.v));
memset(cod.v, 0, sizeof(cod.v));
memset(s.v, 0, sizeof(s.v));
p2.v[0] = 1;
p2.v[1] = 1;
cod.v[0] = 1;
cod.v[1] = 0;
s.v[0] = 1;
s.v[1] = 0;
for(int i = k; i >= 1; i --)
{
if(a[i] != 0)
cod += p2;
p2 += p2;
}
int sum = 5 * n;
for(int i = 0; i <= 255; i ++)
{
int last = 0;
for(int j = 0; j <= n * 5 && j <= sum; j ++)
{
// cout << " SUNTEM IN " << i << " CR " << j << "\n";
if(cod >= s)
last = j;
else
{
s -= dp[255 - i - 1][sum - last];
break;
}
// cout << " URM ADUNS \n";
s += dp[255 - i - 1][sum - j];
// cout << " GATA ADUN\n";
}
//afis(s);
// cout << " PENTRU FRECVENTA LUI " << i << " ESTE " << last << "\n";
sum -= last;
for(int j = 1; j <= last; j ++)
send(i);
}
//cout << "RAMAS == 0: " << sum << "\n";
//afis(cod);
//afis(s);
}
#include "decoder.h"
#include "decoderlib.h"
#include <bits/stdc++.h>
#define MAX_N 64
using namespace std;
int n;
void aduna(unsigned char a[], unsigned char b[])
{
int i = 1;
int t = 0;
for(i = 1; i <= max(a[0], b[0]) || t; i ++)
{
a[i] += b[i] + t;
t = 0;
if(a[i] > 9)
{
t = a[i] / 10;
a[i] %= 10;
}
}
a[0] = i - 1;
}
bool cmp(unsigned char a[], unsigned char b[])
{
if(a[0] > b[0])
return 1;
if(a[0] < b[0])
return 0;
for(int i = a[0]; i >= 1; i --)
{
if(a[i] != b[i])
return (a[i] > b[i]);
}
return 1;
}
void copyV(unsigned char a[], unsigned char b[])
{
for(int i = 1; i <= a[0]; i ++)
a[i] = 0;
a[0] = b[0];
for(int i = 1; i <= b[0]; i ++)
a[i] = b[i];
}
void scade(unsigned char a[], unsigned char b[])
{
int t = 0;
for(int i = 1; i <= b[0] || t; i ++)
{
int x = (int)a[i] - (int)t - (int)b[i];
t = 0;
if(x < 0)
{
t = 1;
x += 10;
}
a[i] = x;
}
while(a[0] > 1 && a[a[0]] == 0)
a[0] --;
}
struct nr
{
unsigned char v[200];
void operator +=(nr &x)
{
aduna(v, x.v);
}
void operator -=(nr &x)
{
scade(v, x.v);
}
void operator =(nr &x)
{
copyV(v, x.v);
}
bool operator >= (nr &x)
{
return cmp(v, x.v);
}
};
nr dp[255 + 1][MAX_N * 5 + 1];
nr sdp[255 + 1][MAX_N * 5 + 1];
nr mdp[255 + 1][MAX_N * 5 + 1];
nr p2;
nr cod;
nr s;
int done;
void getDp()
{
if(done == 1)
return;
done = 1;
dp[0][0].v[0] = 1;
dp[0][0].v[1] = 1;
sdp[0][0].v[0] = 1;
sdp[0][0].v[1] = 1;
// cout << n << "\n";
int nn = 64;
for(int i = 0; i < 255; i ++)
{
for(int j = 0; j <= nn * 5; j ++)
{
// if(i >= 150)
//cout << i << " " << j << " " << n << "\n";
if(j > 0)
{
sdp[i][j] += sdp[i][j - 1];
mdp[i][j] += mdp[i][j - 1];
}
dp[i][j] = sdp[i][j];
dp[i][j] -= mdp[i][j];
if(n == 0)
cout << dp[i][j].v[0] << " " << dp[i][j].v[1] << " " << dp[i][j].v[2] << "\n";
if(dp[i][j].v[0] != 0)
{
sdp[i + 1][j] += dp[i][j];
if(j + 256 <= nn * 5)
mdp[i + 1][j + 256] += dp[i][j];
}
}
}
}
void afis(nr a)
{
for(int i = a.v[0]; i >= 1; i --)
cout << (int)a.v[i];
cout << "\n";
}
void encode(int N, int M[])
{
n = N;
getDp();
int k = 0;
int a[700];
for(int i = 0; i < N; i ++)
{
for(int j = 7; j >= 0; j --)
a[++ k] = (((1 << j) & M[i]) != 0);
}
memset(p2.v, 0, sizeof(p2.v));
memset(cod.v, 0, sizeof(cod.v));
memset(s.v, 0, sizeof(s.v));
p2.v[0] = 1;
p2.v[1] = 1;
cod.v[0] = 1;
cod.v[1] = 0;
s.v[0] = 1;
s.v[1] = 0;
for(int i = k; i >= 1; i --)
{
if(a[i] != 0)
cod += p2;
p2 += p2;
}
int sum = 5 * n;
for(int i = 0; i <= 255; i ++)
{
int last = 0;
for(int j = 0; j <= n * 5 && j <= sum; j ++)
{
// cout << " SUNTEM IN " << i << " CR " << j << "\n";
if(cod >= s)
last = j;
else
{
s -= dp[255 - i - 1][sum - last];
break;
}
// cout << " URM ADUNS \n";
s += dp[255 - i - 1][sum - j];
// cout << " GATA ADUN\n";
}
//afis(s);
// cout << " PENTRU FRECVENTA LUI " << i << " ESTE " << last << "\n";
sum -= last;
for(int j = 1; j <= last; j ++)
send(i);
}
//cout << "RAMAS == 0: " << sum << "\n";
//afis(cod);
//afis(s);
}
nr p[600];
nr sp;
nr tmp;
int apel;
void decode(int N, int L, int X[])
{
n = N;
getDp();
int ap[256];
for(int i = 0; i <= 255; i ++)
ap[i] = 0;
for(int i = 0; i < L; i ++)
ap[X[i]] ++;
memset(s.v, 0, sizeof(s.v));
int sum = 5 * n;
for(int i = 0; i <= 255; i ++)
{
int last = 0;
for(int j = 0; j < ap[i]; j ++)
s += dp[255 - i - 1][sum - j];
sum -= ap[i];
}
apel ++;
if(apel == 1)
{
p[0].v[0] = 1;
p[0].v[1] = 1;
for(int i = 1; i <= 520; i ++)
{
p[i].v[0] = 1;
p[i].v[1] = 0;
p[i] += p[i - 1];
p[i] += p[i - 1];
}
}
memset(sp.v, 0, sizeof(sp.v));
sp.v[0] = 1;
sp.v[1] = 0;
int a[600];
memset(a, 0, sizeof(a));
for(int i = n * 8 - 1; i >= 0; i --)
{
tmp = sp;
tmp += p[i];
if(s >= tmp)
{
sp += p[i];
a[i] = 1;
}
}
for(int i = n * 8 - 1; i >= 0; i -= 8)
{
int nr = 0;
for(int x = 7, j = 0; x >= 0; x --, j ++)
nr += (a[i - j] << x);
output(nr);
}
}