Submission #396985

#TimeUsernameProblemLanguageResultExecution timeMemory
396985two_sidesParrots (IOI11_parrots)C++17
81 / 100
13 ms1336 KiB
#include "encoder.h" #include "encoderlib.h" #include <bits/stdc++.h> using namespace std; void encode(int N, int M[]) { int P3[] = {0, 1, 3, 9, 27, 2, 4, 6, 10, 12, 18, 28, 30, 36, 54, 5, 7, 11, 13, 15, 19, 21, 29, 31, 33, 37, 39, 45, 55, 57, 63, 8, 14, 16, 20, 22, 24, 32, 34, 38, 40, 42, 46, 48, 56, 58, 60, 64, 66, 72, 17, 23, 25, 35, 41, 43, 47, 49, 51, 59, 61, 65, 67, 69}; int A[81], P2[64]; if (N == 1) return send(M[0]); if (N > 52) { for (int i = 0; i < N; i++) { A[P3[i]] = M[i]; send(M[i]); send(M[i]); send(M[i]); } sort(P3, P3 + N, [&](int i, int j) { return A[i] < A[j]; }); for (int i = 0; i + 1 < N; i++) { int x = P3[i]; for (int j = 0; j < 4; j++) { int y = x % 3; while (y--) send(i * 4 + j); x /= 3; } } } else { int l = 0; while ((1 << l) < N) l++; iota(P2, P2 + (1 << l), 0); sort(P2, P2 + (1 << l), [](int i, int j) { return __builtin_popcount(i) < __builtin_popcount(j); }); for (int i = 0; i < N; i++) { A[P2[i]] = M[i]; send(M[i]); send(M[i]); } sort(P2, P2 + N, [&](int i, int j) { return A[i] < A[j]; }); for (int i = 0; i + 1 < N; i++) { int x = P2[i]; for (int j = 0; j < l; j++) { assert(i * l + j < 256); if (x & 1) send(i * l + j); x >>= 1; } } } }
#include "decoder.h" #include "decoderlib.h" #include <bits/stdc++.h> using namespace std; void decode(int N, int L, int X[]) { int P2[] = {0, 1, 2, 4, 8, 16, 32, 3, 5, 6, 9, 10, 12, 17, 18, 20, 24, 33, 34, 36, 40, 48, 7, 11, 13, 14, 19, 21, 22, 25, 26, 28, 35, 37, 38, 41, 42, 44, 49, 50, 52, 56, 15, 23, 27, 29, 30, 39, 43, 45, 46, 51, 53, 54, 57, 58, 60, 31, 47, 55, 59, 61, 62, 63}; int P3[] = {0, 1, 3, 9, 27, 2, 4, 6, 10, 12, 18, 28, 30, 36, 54, 5, 7, 11, 13, 15, 19, 21, 29, 31, 33, 37, 39, 45, 55, 57, 63, 8, 14, 16, 20, 22, 24, 32, 34, 38, 40, 42, 46, 48, 56, 58, 60, 64, 66, 72, 17, 23, 25, 35, 41, 43, 47, 49, 51, 59, 61, 65, 67, 69}; int A[81], C[256], M[64]; memset(A, -1, sizeof A); memset(C, 0, sizeof C); if (N == 1) return output(X[0]); for (int i = 0; i < L; i++) C[X[i]]++; if (N > 52) { for (int i = 0, j = 0; i < 256; i++) { int x = C[i] / 3; while (x--) M[j++] = i; } for (int i = 0; i + 1 < N; i++) { int x = 0; for (int j = 3; j >= 0; j--) x = x * 3 + C[i * 4 + j] % 3; A[x] = M[i]; } for (int i = 0; i < N; i++) if (A[P3[i]] >= 0) output(A[P3[i]]); else output(M[N - 1]); } else { int l = 0; while ((1 << l) < N) l++; iota(P2, P2 + (1 << l), 0); sort(P2, P2 + (1 << l), [](int i, int j) { return __builtin_popcount(i) < __builtin_popcount(j); }); for (int i = 0, j = 0; i < 256; i++) { int x = C[i] >> 1; while (x--) M[j++] = i; } for (int i = 0; i + 1 < N; i++) { int x = 0; for (int j = l - 1; j >= 0; j--) x = (x << 1) + (C[i * l + j] & 1); A[x] = M[i]; } for (int i = 0; i < N; i++) if (A[P2[i]] >= 0) output(A[P2[i]]); else output(M[N - 1]); } }
#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...