Submission #574068

#TimeUsernameProblemLanguageResultExecution timeMemory
574068VanillaParrots (IOI11_parrots)C++17
100 / 100
68 ms56048 KiB
// pasol nahui eu am facut-o pe 98 si m-am zb #include "encoder.h" #include "encoderlib.h" #include <bits/stdc++.h> #define FOR(i,l,r) for(int i=(l); i<=(r); ++i) #define REP(i,l,r) for(int i=(l); i<(r); ++i) #define FORD(i,r,l) for(int i=(r); i>=(l); --i) #define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i) #define getbit(x, i) (((x) >> (i)) & 1) #define MASK(i) (1 << (i)) using namespace std; /// BigNum const long long MOD = (long long)1e16; typedef vector<long long> BigNum; bool operator < (BigNum A, BigNum B) { if (A.size() != B.size()) return A.size() < B.size(); REPD(i, (int)A.size(), 0) if (A[i] != B[i]) return A[i] < B[i]; return false; } bool operator <= (BigNum A, BigNum B) { if (A.size() != B.size()) return A.size() < B.size(); REPD(i, (int)A.size(), 0) if (A[i] != B[i]) return A[i] < B[i]; return true; } BigNum operator + (BigNum A, BigNum B) { BigNum C(max(A.size(), B.size())); long long carry = 0; REP(i, 0, C.size()) { if (i < A.size()) carry += A[i]; if (i < B.size()) carry += B[i]; C[i] = carry % MOD; carry /= MOD; } if (carry) C.push_back(carry); return C; } BigNum operator + (BigNum A, int B) { return A + BigNum{B}; } BigNum operator * (BigNum A, int B) { long long carry = 0; for(long long &v : A) { carry += v * B; v = carry % MOD; carry /= MOD; } if (carry) A.push_back(carry); return A; } BigNum operator / (BigNum A, int B) { long long carry = 0; REPD(i, (int)A.size(), 0) { carry = carry * MOD + A[i]; A[i] = carry / B; carry %= B; } while (!A.empty() && A.back() == 0) A.pop_back(); return A; } BigNum C[1000][1000]; BigNum getC(int n, int k) { if (C[n][k].size()) return C[n][k]; if (k == 0) return C[n][k] = {1}; if (k > n) return {}; return C[n][k] = getC(n - 1, k) + getC(n - 1, k - 1); } void encode(int n, int a[]) { int c[n * 8], code[n * 5]; int num = 0; REP(i, 0, n) { REP(j, 0, 8) { c[i * 8 + j] = getbit(a[i], j); } } int sz = n * 5; BigNum order = {1}; REP(i, 0, n*8) order = order * 2 + c[i]; auto get = [&](int n, int k) -> BigNum {/// x1 + x2 + ... + xk = n -> C(n + k - 1, k - 1) return getC(n + k - 1, k - 1); }; int prv = 0; BigNum sum = {0}; REP(i, 0, sz) { while (sum + get(sz - i - 1, 256 - prv) <= order) { sum = sum + get(sz - i - 1, 256 - prv); ++prv; } code[i] = prv; } REP(i, 0, sz) send(code[i]); }
// pasol nahui eu am facut-o pe 98 si m-am zb #include "decoder.h" #include "decoderlib.h" #include <bits/stdc++.h> #define FOR(i,l,r) for(int i=(l); i<=(r); ++i) #define REP(i,l,r) for(int i=(l); i<(r); ++i) #define FORD(i,r,l) for(int i=(r); i>=(l); --i) #define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i) #define getbit(x, i) (((x) >> (i)) & 1) #define MASK(i) (1 << (i)) using namespace std; /// BigNum const long long MOD = (long long)1e16; typedef vector<long long> BigNum; bool operator < (BigNum A, BigNum B) { if (A.size() != B.size()) return A.size() < B.size(); REPD(i, (int)A.size(), 0) if (A[i] != B[i]) return A[i] < B[i]; return false; } bool operator <= (BigNum A, BigNum B) { if (A.size() != B.size()) return A.size() < B.size(); REPD(i, (int)A.size(), 0) if (A[i] != B[i]) return A[i] < B[i]; return true; } BigNum operator + (BigNum A, BigNum B) { BigNum C(max(A.size(), B.size())); long long carry = 0; REP(i, 0, C.size()) { if (i < A.size()) carry += A[i]; if (i < B.size()) carry += B[i]; C[i] = carry % MOD; carry /= MOD; } if (carry) C.push_back(carry); return C; } BigNum operator + (BigNum A, int B) { return A + BigNum{B}; } BigNum operator * (BigNum A, int B) { long long carry = 0; for(long long &v : A) { carry += v * B; v = carry % MOD; carry /= MOD; } if (carry) A.push_back(carry); return A; } BigNum operator / (BigNum A, int B) { long long carry = 0; REPD(i, (int)A.size(), 0) { carry = carry * MOD + A[i]; A[i] = carry / B; carry %= B; } while (!A.empty() && A.back() == 0) A.pop_back(); return A; } BigNum C[1000][1000]; BigNum getC(int n, int k) { if (C[n][k].size()) return C[n][k]; if (k == 0) return C[n][k] = {1}; if (k > n) return {}; return C[n][k] = getC(n - 1, k) + getC(n - 1, k - 1); } void decode(int n, int sz, int b[]) { sort(b, b + sz); vector<int> a(n, 0); auto get = [&](int n, int k) -> BigNum {/// x1 + x2 + ... + xk = n -> C(n + k - 1, k - 1) return getC(n + k - 1, k - 1); }; BigNum order = {0}; int prv = 0; REP(i, 0, sz) { while (prv < b[i]) { order = order + get(sz - i - 1, 256 - prv); ++prv; } } REPD(i, n*8, 0) { if (order.size() && order[0] % 2 == 1) a[i / 8] += MASK(i % 8); order = order / 2; } REP(i, 0, n) output(a[i]); }

Compilation message (stderr)

encoder.cpp: In function 'BigNum operator+(BigNum, BigNum)':
encoder.cpp:6:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define REP(i,l,r) for(int i=(l); i<(r); ++i)
      |                                    ^
encoder.cpp:32:5: note: in expansion of macro 'REP'
   32 |     REP(i, 0, C.size()) {
      |     ^~~
encoder.cpp:33:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         if (i < A.size()) carry += A[i];
      |             ~~^~~~~~~~~~
encoder.cpp:34:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         if (i < B.size()) carry += B[i];
      |             ~~^~~~~~~~~~
encoder.cpp: In function 'void encode(int, int*)':
encoder.cpp:79:9: warning: unused variable 'num' [-Wunused-variable]
   79 |     int num = 0;
      |         ^~~

decoder.cpp: In function 'BigNum operator+(BigNum, BigNum)':
decoder.cpp:6:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    6 | #define REP(i,l,r) for(int i=(l); i<(r); ++i)
      |                                    ^
decoder.cpp:32:5: note: in expansion of macro 'REP'
   32 |     REP(i, 0, C.size()) {
      |     ^~~
decoder.cpp:33:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |         if (i < A.size()) carry += A[i];
      |             ~~^~~~~~~~~~
decoder.cpp:34:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |         if (i < B.size()) carry += B[i];
      |             ~~^~~~~~~~~~
#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...