제출 #233699

#제출 시각아이디문제언어결과실행 시간메모리
233699Coroian_David앵무새 (IOI11_parrots)C++11
0 / 100
2100 ms129272 KiB
#include "encoder.h" #include "encoderlib.h" #include <bits/stdc++.h> using namespace std; int n; int OK = 0; void aduan2(int a[], int b[]) { // cout << " ADUN " << a[0] << " " << b[0] << "\n"; // cout << a[1] << " " << b[1] << " " << a[2] << " " << b[2] << "\n"; /*if(a[0] == 0) { memset(a, 0, sizeof(a)); for(int i = 0; i <= 199; i ++) a[i] = 0; }*/ int i = 1; int t = 0; for(i = 1; i <= max(a[0], b[0]) || t; i ++) { //if(OK) //cout << " SUTNEM " << i << " " << a[i] << " " << b[i] << " " << t << "\n"; a[i] += b[i] + t; t = 0; if(a[i] > 9) { t = a[i] / 10; a[i] %= 10; } } //cout << a[0] << " " << i-1 << "\n"; a[0] = i - 1; } bool cm2(int a[], int 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 copiv(int a[], int 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 scad(int a[], int b[]) { int t = 0; for(int i = 1; i <= b[0] || t; i ++) { a[i] = a[i] - t - b[i]; t = 0; if(a[i] < 0) { t = 1; a[i] += 10; } } while(a[0] > 1 && a[a[0]] == 0) a[0] --; } struct nr { int v[200]; void operator +=(nr &x) { aduan2(v, x.v); } void operator -=(nr &x) { scad(v, x.v); } void operator =(nr &x) { copiv(v, x.v); } bool operator >= (nr &x) { return cm2(v, x.v); } }; //#define 64 64 nr a, b; nr p2; nr cod; nr s; nr dp[255 + 1][64 * 5 + 1]; nr sumdp[255 + 1][64 * 5 + 1]; int okk; void faDp() { if(okk == 1) return; // cout << "TINRA DP\n"; /* for(int i = 0; i <= 255; i ++) { for(int j = 0; j <= 320; j ++) { memset(dp[i][j].v, 0, sizeof(dp[i][j].v)); memset(sumdp[i][j].v, 0, sizeof(sumdp[i][j].v)); } }*/ okk = 1; dp[0][0].v[0] = 1; dp[0][0].v[1] = 1; for(int i = 0; i < 255; i ++) { for(int j = 0; j <= 64 * 5; j ++) { //cout << i << " " << j << " " << dp[i][j].v[0] << "\n"; if(i == 1 && j == 256) OK = 1; else OK = 0; if(j > 0) { // cout << " ADUN LA SUMP " << i << " " << j << " PE " << i << " " << j - 1 << "\n"; sumdp[i][j] += sumdp[i][j - 1]; } OK = 0; // cout << " ADUN LA I J pe usmp i j \n"; dp[i][j] += sumdp[i][j]; if(dp[i][j].v[0] != 0) { // cout << " ADUN LA URM " << i + 1 << " " << j << " PE " << i << " " << j << "\n"; sumdp[i + 1][j] += dp[i][j]; if(j + 256 <= 64 * 5) { // cout << " AVEM " << j+256 << " SI SCADEM DIN " << i + 1 << " \n"; sumdp[i + 1][j + 256] -= dp[i][j]; } } } } // cout << "GATRA DP\n"; } /* void afis(nr a) { for(int i = a.v[0]; i >= 1; i --) cout << a.v[i]; cout << "\n"; }*/ void encode(int N, int M[]) { //cout << "TINRA ECONDE\n"; n = N; faDp(); 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; 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"; } // 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> using namespace std; int nn; void aduna(int a[], int b[]) { // cout << " ADUN " << a[0] << " " << b[0] << "\n"; // cout << a[1] << " " << b[1] << " " << a[2] << " " << b[2] << "\n"; int i = 1; int t = 0; for(i = 1; i <= max(a[0], b[0]) || t; i ++) { // cout << " SUTNEM " << i << "\n"; a[i] += b[i] + t; t = 0; if(a[i] > 9) { t = a[i] / 10; a[i] %= 10; } } //cout << a[0] << " " << i-1 << "\n"; a[0] = i - 1; } bool cmp(int a[], int 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(int a[], int 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(int a[], int b[]) { int t = 0; for(int i = 1; i <= b[0] || t; i ++) { a[i] = a[i] - t - b[i]; t = 0; if(a[i] < 0) { t = 1; a[i] += 10; } } while(a[0] > 1 && a[a[0]] == 0) a[0] --; } struct nr { int 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); } }; //#define 64 64 nr dpp[255 + 1][64 * 5 + 1]; nr ssdpp[255 + 1][64 * 5 + 1]; nr p22; nr codd; nr ss; int doneDp; void getdpp() { if(doneDp == 1) return; doneDp = 1; dpp[0][0].v[0] = 1; dpp[0][0].v[1] = 1; for(int i = 0; i < 255; i ++) { for(int j = 0; j <= nn * 5; j ++) { if(j > 0) ssdpp[i][j] += ssdpp[i][j - 1]; dpp[i][j] += ssdpp[i][j]; if(dpp[i][j].v[0] != 0) { ssdpp[i + 1][j] += dpp[i][j]; if(j + 256 <= nn * 5) ssdpp[i + 1][j + 256] -= dpp[i][j]; } } } } nr p[600]; nr sp; nr tmp; int doneP; void getPs() { if(doneP == 1) return; doneP = 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]; } } void decode(int N, int L, int X[]) { cout << " INTRA DECODe\n"; nn = N; getdpp(); int ap[256]; for(int i = 0; i <= 255; i ++) ap[i] = 0; for(int i = 0; i < L; i ++) ap[X[i]] ++; memset(ss.v, 0, sizeof(ss.v)); memset(sp.v, 0, sizeof(sp.v)); memset(tmp.v, 0, sizeof(tmp.v)); int sum = 5 * nn; for(int i = 0; i <= 255; i ++) { // if(ap[i] > 0) // cout << i <<"APRAE " << ap[i] << "\n"; int last = 0; for(int j = 0; j < ap[i]; j ++) ss += dpp[255 - i - 1][sum - j]; sum -= ap[i]; } //cout << " CODUL ESTE : "; // afis(s); getPs(); sp.v[0] = 1; sp.v[1] = 0; int a[600]; memset(a, 0, sizeof(a)); for(int i = nn * 8 - 1; i >= 0; i --) { tmp = sp; tmp += p[i]; if(ss >= tmp) { sp += p[i]; a[i] = 1; } } // cout << "\n"; for(int i = nn * 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); } cout << "GATA DECODE\n"; }

컴파일 시 표준 에러 (stderr) 메시지

decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:199:13: warning: unused variable 'last' [-Wunused-variable]
         int last = 0;
             ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...