제출 #235571

#제출 시각아이디문제언어결과실행 시간메모리
235571Coroian_David앵무새 (IOI11_parrots)C++11
0 / 100
2108 ms386336 KiB
#include "encoder.h" #include "encoderlib.h" #include <bits/stdc++.h> #define MAX_N 64 using namespace std; int n; 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 MAX_N 64 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 a, b; nr p2; nr cod; nr s; /* void afis(int a[]) { for(int i = a[0]; i >=1; i --) cout << a[i]; cout << "\n"; }*/ void getDp() { dp[0][0].v[0] = 1; dp[0][0].v[1] = 1; sdp[0][0].v[0] = 1; sdp[0][0].v[1] = 1; int n = 64; for(int i = 0; i < 255; i ++) { for(int j = 0; j <= n * 5; j ++) { 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(dp[i][j].v[0] != 0) { sdp[i + 1][j] += dp[i][j]; if(j + 256 <= n * 5) mdp[i + 1][j + 256] += dp[i][j]; } } } } /* 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[]) { 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); } 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> #define MAX_N 64 using namespace std; int n; 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 MAX_N 64 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 a, b; nr p2; nr cod; nr s; /* void afis(int a[]) { for(int i = a[0]; i >=1; i --) cout << a[i]; cout << "\n"; }*/ void getDp() { dp[0][0].v[0] = 1; dp[0][0].v[1] = 1; sdp[0][0].v[0] = 1; sdp[0][0].v[1] = 1; int n = 64; for(int i = 0; i < 255; i ++) { for(int j = 0; j <= n * 5; j ++) { 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(dp[i][j].v[0] != 0) { sdp[i + 1][j] += dp[i][j]; if(j + 256 <= n * 5) mdp[i + 1][j + 256] += dp[i][j]; } } } } nr p[600]; nr sp; nr tmp; 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 ++) { // if(ap[i] > 0) // cout << i <<"APRAE " << ap[i] << "\n"; int last = 0; for(int j = 0; j < ap[i]; j ++) s += dp[255 - i - 1][sum - j]; sum -= ap[i]; } //cout << " CODUL ESTE : "; // afis(s); 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]; } 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; } } // cout << "\n"; 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); } }

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

decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:185:21: 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...