제출 #199362

#제출 시각아이디문제언어결과실행 시간메모리
199362alexandra_udristoiu앵무새 (IOI11_parrots)C++14
100 / 100
634 ms66800 KiB
#include<iostream> #include<cstring> #include "encoder.h" #include "encoderlib.h" #define base 5000000 using namespace std; static int d[350][260][100], pt[70][100], num[100]; static void adun(int a[], int b[], int c[]){ int i, t = 0; c[0] = max(a[0], b[0]); for(i = 1; i <= c[0]; i++){ c[i] = t + a[i] + b[i]; t = c[i] / base; c[i] %= base; } if(t != 0){ c[ ++c[0] ] = t; } } static void mult(int a[], int x, int b[]){ int i, t = 0; b[0] = a[0]; for(i = 1; i <= a[0]; i++){ b[i] = a[i] * x + t; t = b[i] / base; b[i] %= base; } while(t != 0){ b[ ++b[0] ] = t % base; t /= base; } } static void scad(int a[], int b[]){ int i, t = 0; for(i = 1; i <= a[0]; i++){ if(a[i] < b[i] + t){ a[i] = a[i] + base - b[i] - t; t = 1; } else{ a[i] -= b[i] + t; t = 0; } } while(a[0] > 1 && a[ a[0] ] == 0){ a[0]--; } } static int comp(int a[], int b[]){ if(a[0] != b[0]){ if(a[0] < b[0]){ return 1; } return 0; } for(int i = a[0]; i >= 1; i--){ if(a[i] != b[i]){ if(a[i] < b[i]){ return 1; } return 0; } } return 0; } static void calcpt(int n){ pt[0][0] = 1; pt[0][1] = 1; for(int i = 1; i <= n; i++){ mult(pt[i - 1], 256, pt[i]); } } static void calcdp(int n){ int i, j; memset(num, 0, sizeof(num) ); for(j = 0; j < 256; j++){ d[n - 1][j][0] = d[n - 1][j][1] = 1; } for(i = n - 2; i >= 0; i--){ for(j = 255; j >= 0; j--){ adun(d[i + 1][j], d[i][j + 1], d[i][j]); } } } void encode(int n, int v[]){ int i, j, x, k = 5 * n - 1; calcdp(k); calcpt(n); for(i = 0; i < n; i++){ for(j = 0; j < v[i]; j++){ adun(num, pt[n - i - 1], num); } } adun(num, pt[0], num); x = 0; for(i = 0; i < k; i++){ while( comp(d[i][x], num) ){ scad(num, d[i][x]); x++; } send(x); } }
#include<iostream> #include<algorithm> #include<cstring> #define base 5000000 #include "decoder.h" #include "decoderlib.h" using namespace std; static int d[350][260][100], pt[70][100], num[100]; static void adun(int a[], int b[], int c[]){ int i, t = 0; c[0] = max(a[0], b[0]); for(i = 1; i <= c[0]; i++){ c[i] = t + a[i] + b[i]; t = c[i] / base; c[i] %= base; } if(t != 0){ c[ ++c[0] ] = t; } } static void mult(int a[], int x, int b[]){ int i, t = 0; b[0] = a[0]; for(i = 1; i <= a[0]; i++){ b[i] = a[i] * x + t; t = b[i] / base; b[i] %= base; } while(t != 0){ b[ ++b[0] ] = t % base; t /= base; } } static void scad(int a[], int b[]){ int i, t = 0; for(i = 1; i <= a[0]; i++){ if(a[i] < b[i] + t){ a[i] = a[i] + base - b[i] - t; t = 1; } else{ a[i] -= b[i] + t; t = 0; } } while(a[0] > 1 && a[ a[0] ] == 0){ a[0]--; } } static int comp(int a[], int b[]){ if(a[0] != b[0]){ if(a[0] < b[0]){ return 1; } return 0; } for(int i = a[0]; i >= 1; i--){ if(a[i] != b[i]){ if(a[i] < b[i]){ return 1; } return 0; } } return 0; } static void calcpt(int n){ pt[0][0] = 1; pt[0][1] = 1; for(int i = 1; i <= n; i++){ mult(pt[i - 1], 256, pt[i]); } } static void calcdp(int n){ int i, j; for(j = 0; j < 256; j++){ d[n - 1][j][0] = d[n - 1][j][1] = 1; } for(i = n - 2; i >= 0; i--){ for(j = 255; j >= 0; j--){ adun(d[i + 1][j], d[i][j + 1], d[i][j]); } } } void decode(int n, int k, int v[]){ int i, x, j; memset(num, 0, sizeof(num) ); calcpt(n); calcdp(k); sort(v, v + k); for(j = 0; j < v[i]; j++){ adun(num, d[0][j], num); } for(i = 1; i < k; i++){ for(j = v[i - 1]; j < v[i]; j++){ adun(num, d[i][j], num); } } adun(num, pt[0], num); for(i = 0; i < n; i++){ for(j = 0; j < 256; j++){ if(comp(pt[n - i - 1], num) == 0){ output(j); break; } else{ scad(num, pt[n - i - 1]); } } } }

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

decoder.cpp: In function 'void decode(int, int, int*)':
decoder.cpp:85:12: warning: unused variable 'x' [-Wunused-variable]
     int i, x, j;
            ^
decoder.cpp:90:23: warning: 'i' is used uninitialized in this function [-Wuninitialized]
     for(j = 0; j < v[i]; j++){
                       ^
#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...