Submission #711719

#TimeUsernameProblemLanguageResultExecution timeMemory
711719becaidoPopcount (COCI19_popcount)C++17
110 / 110
2 ms344 KiB
#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx,popcnt,sse4,abm") #include <bits/stdc++.h> using namespace std; #ifdef WAIMAI #define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE) void dout() {cout << '\n';} template<typename T, typename...U> void dout(T t, U...u) {cout << t << (sizeof... (u) ? ", " : ""), dout (u...);} #else #define debug(...) 7122 #endif #define ll long long #define Waimai ios::sync_with_stdio(false), cin.tie(0) #define FOR(x,a,b) for (int x = a, I = b; x <= I; x++) #define pb emplace_back #define F first #define S second struct bigint : vector<int> { const static int base = 1e9, wid = log10(base); bool neg = false; bigint() {} bigint(string s) { if (s == "-0") { emplace_back(0); return; } if (s[0] == '-') { neg = true; s = s.substr(1); } for (int i = s.size() - 1, cnt = 0, val = 0, ten = 1; i >= 0; i--) { cnt++; val += (s[i] - '0') * ten; ten *= 10; if (i == 0 || cnt == wid) { emplace_back(val); cnt = val = 0; ten = 1; } } } template<typename T> bigint(const T& val) : bigint(to_string(val)) {} template<typename T> bigint& operator = (const T &rhs) { *this = bigint(rhs); return *this; } template<typename T> operator T() { stringstream ss; ss << *this; T re; ss >> re; return re; } int abscmp(const bigint& rhs) const { if (size() != rhs.size()) { return size() > rhs.size() ? 1 : -1; } for (int i = size() - 1; i >= 0; i--) { if ((*this)[i] != rhs[i]) { return (*this)[i] > rhs[i] ? 1 : -1; } } return 0; } int cmp(const bigint& rhs) const { if (neg != rhs.neg) { return neg == true ? -1 : 1; } return neg == true ? -abscmp(rhs) : abscmp(rhs); } bool operator < (const bigint& rhs) const { return cmp(rhs) < 0; } bool operator > (const bigint& rhs) const { return cmp(rhs) > 0; } bool operator <= (const bigint& rhs) const { return cmp(rhs) <= 0; } bool operator >= (const bigint& rhs) const { return cmp(rhs) >= 0; } bool operator == (const bigint& rhs) const { return cmp(rhs) == 0; } bool operator != (const bigint& rhs) const { return cmp(rhs) != 0; } bigint& operator += (const bigint& rhs) { return *this = *this + rhs; } bigint& operator ++ () { return *this = *this + 1; } bigint& operator -= (const bigint& rhs) { return *this = *this - rhs; } bigint& operator -- () { return *this = *this - 1; } bigint& operator *= (const bigint& rhs) { return *this = *this * rhs; } bigint& operator /= (const bigint& rhs) { return *this = *this / rhs; } bigint& operator %= (const bigint& rhs) { return *this = *this % rhs; } bigint abs() const { bigint re = *this; re.neg = false; return re; } void carry() { emplace_back(0); for (int i = 0; i < size(); i++) { if ((*this)[i] < 0) { (*this)[i] += base; (*this)[i + 1]--; } if ((*this)[i] >= base) { (*this)[i] -= base; (*this)[i + 1]++; } } while (size() && back() == 0) { pop_back(); } if (size() == 0) { neg = false; emplace_back(0); } } bigint operator -() const { if (*this == 0) { return *this; } bigint re = *this; re.neg ^= 1; return re; } friend bigint operator + (bigint lhs, bigint rhs) { if (lhs.neg == true) { return -(-lhs + -rhs); } if (rhs.neg == true) { return lhs - -rhs; } if (lhs.size() < rhs.size()) { lhs.resize(rhs.size(), 0); } for (int i = 0; i < rhs.size(); i++) { lhs[i] += rhs[i]; } lhs.carry(); return lhs; } friend bigint operator - (bigint lhs, bigint rhs) { if (lhs.neg == true) { return -(-lhs - -rhs); } if (rhs.neg == true) { return lhs + -rhs; } if (lhs.abscmp(rhs) < 0) { return -(rhs - lhs); } for (int i = 0; i < rhs.size(); i++) { lhs[i] -= rhs[i]; } lhs.carry(); return lhs; } friend bigint operator * (bigint lhs, bigint rhs) { if (lhs == 0 || rhs == 0) { return 0; } bigint re; re.neg = lhs.neg ^ rhs.neg; vector<long long> tmp; auto add = [&](int i, long long val) { while (i >= tmp.size()) { tmp.emplace_back(0); } tmp[i] += val; }; for (int i = 0; i < lhs.size(); i++) { for (int j = 0; j < rhs.size(); j++) { add(i + j, 1ll * lhs[i] * rhs[j]); } for (int j = 0; j < tmp.size(); j++) { if (tmp[j] >= base) { add(j + 1, tmp[j] / base); tmp[j] %= base; } } } re.resize(tmp.size()); for (int i = 0; i < tmp.size(); i++) { re[i] = tmp[i]; } return re; } friend bigint operator / (bigint lhs, bigint rhs) { assert(rhs != 0); if (lhs == 0) { return 0; } int norm = base / (rhs.back() + 1); bigint x = lhs.abs() * norm; bigint y = rhs.abs() * norm; bigint q, r; q.resize(x.size()); for (int i = x.size() - 1; i >= 0; i--) { r = r * base + x[i]; int s1 = r.size() <= y.size() ? 0 : r[y.size()]; int s2 = r.size() < y.size() ? 0 : r[y.size() - 1]; int d = (1ll * base * s1 + s2) / y.back(); r = r - y * d; while (r.neg == true) { r += y; d--; } q[i] = d; } q.neg = lhs.neg ^ rhs.neg; q.carry(); return q; } friend bigint operator % (bigint lhs, bigint rhs) { return lhs - (lhs / rhs) * rhs; } friend istream& operator >> (istream& ss, bigint& val) { string s; ss >> s; val = s; return ss; } friend ostream& operator << (ostream& ss, const bigint& val) { if (val.neg == true) { ss << '-'; } ss << val.back(); for (int i = (int)val.size() - 2; i >= 0; i--) { ss << string(wid - to_string(val[i]).size(), '0') << val[i]; } return ss; } }; bigint two[512]; int n, k; void solve() { cin >> n >> k; if (n == 1) { cout << "1\n"; cout << "A=A\n"; return; } int m = __lg(n - 1) + 1; cout << m << '\n'; two[0] = 1; FOR (i, 1, 511) two[i] = two[i - 1] * 2; for (int len = 1, i = 0; len < n; len <<= 1, i++) { bigint sum = 0; for (int j = 0; j < n; j += 2 * len) FOR (k, j, j + len - 1) if (k < n) sum += two[k]; cout << "A=" << "((A&" << sum << ")+((A>>" << len << ")&" << sum << "))\n"; } } int main() { Waimai; solve(); }

Compilation message (stderr)

popcount.cpp: In member function 'void bigint::carry()':
popcount.cpp:124:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |         for (int i = 0; i < size(); i++) {
      |                         ~~^~~~~~~~
popcount.cpp: In function 'bigint operator+(bigint, bigint)':
popcount.cpp:160:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |         for (int i = 0; i < rhs.size(); i++) {
      |                         ~~^~~~~~~~~~~~
popcount.cpp: In function 'bigint operator-(bigint, bigint)':
popcount.cpp:176:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  176 |         for (int i = 0; i < rhs.size(); i++) {
      |                         ~~^~~~~~~~~~~~
popcount.cpp: In lambda function:
popcount.cpp:190:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  190 |             while (i >= tmp.size()) {
      |                    ~~^~~~~~~~~~~~~
popcount.cpp: In function 'bigint operator*(bigint, bigint)':
popcount.cpp:195:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  195 |         for (int i = 0; i < lhs.size(); i++) {
      |                         ~~^~~~~~~~~~~~
popcount.cpp:196:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  196 |             for (int j = 0; j < rhs.size(); j++) {
      |                             ~~^~~~~~~~~~~~
popcount.cpp:199:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  199 |             for (int j = 0; j < tmp.size(); j++) {
      |                             ~~^~~~~~~~~~~~
popcount.cpp:207:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  207 |         for (int i = 0; i < tmp.size(); 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...