Submission #493919

#	Time	Username	Problem	Language	Result	Execution time	Memory
493919		hohohaha	Popcount (COCI19_popcount)	C++14	0 / 110	1 ms	332 KiB

popcount

// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")

#include "bits/stdc++.h"
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;

#define li long long
#define ld long double
#define ii pair<int, int>
#define vi vector<int> 
#define vvi vector<vi>


#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define eb emplace_back
#define em emplace
#define ob pop_back
#define om pop
#define of pop_front

#define fr front
#define bc back

#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); ++i)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); --i)

#define all(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
#define bitc __builtin_popcountll

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand rng
#define endl '\n'
//#define sp ' '

#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

void solve();

signed main() {
// freopen("input.inp","r",stdin);
// freopen("output.out","w",stdout);
   fastio();
   int tc = 1;
   fori(test, 1, tc) {
      solve();
   }
   return 0;
}

//#define int long long
const ld pi = 4 * atan(1.0), eps = 1e-9;

const int Dig = 10;
 
//struct bigint {
//	deque<int> num;
//	int sign = 1;
// 
//	//constructor
//	bigint() {
//	}
//	bigint(long long x) {
//		num.clear();
//		if (x < 0)
//			sign = -1, x = -x;
//		if (x == 0)
//			num.push_back(x);
//		while (x > 0) {
//			num.push_back(x % Dig);
//			x /= Dig;
//		}
//	}
//	bigint(int x) {
//		num.clear();
//		if (x < 0)
//			sign = -1, x = -x;
//		if (x == 0)
//			num.push_back(x);
//		while (x > 0) {
//			num.push_back(x % Dig);
//			x /= Dig;
//		}
//	}
//	bigint(const bigint &x) {
//		sign = x.sign;
//		num = x.num;
//	}
// 
//	// change to int
//	friend int BtoI(const bigint &x) {
//		int res = 0, t = 1;
//		for (int i = 0; i < x.num.size(); i++)
//			res += t * x.num[i];
//		return res;
// 
//	}
// 
//	//absolut
//	friend bigint abs(const bigint &x) {
//		bigint res = x;
//		res.sign = 1;
//		return res;
//	}
// 
//	//clear 0
//	void clr() {
//		while (!num.empty() and !num.back())
//			num.pop_back();
//	}
// 
//	//normalize
//	void normalize() {
//		(*this).clr();
//		int carry = 0;
//		for (int i = 0; i < num.size(); i++) {
//			int t = num[i] + carry;
//			if (t < 0) {
//				t += Dig;
//				carry = -1;
//				num[i] = t;
//			}
//			else {
//				num[i] = t % Dig;
//				carry = t / Dig;
//			}
//		}
//		if (carry > 0)
//			num.push_back(carry);
//		if (carry < 0) {
//			sign *= -1;
//			num.push_back(-carry);
//		}
//		(*this).clr();
//		if (num.empty())
//			sign = 1;
// 
//	}
// 
//	//is 0
//	bool isZero() {
//		(*this).normalize();
//		return num.empty();
//	}
// 
//	//compare operators
//	bool operator<(const bigint &x) const {
//		bigint a = (*this);
//		bigint b = x;
//		a.normalize();
//		b.normalize();
//		if (a.sign != b.sign)
//			return a.sign < b.sign;
//		bool res = false, flag = false;
//		if (a.num.size() != b.num.size()) {
//			res = (a.num.size() < b.num.size());
//			flag = true;
//		}
//		else {
//			for (int i = a.num.size() - 1; i >= 0; i--)
//				if (a.num[i] != b.num[i]) {
//					flag = true;
//					res = (a.num[i] < b.num[i]);
//					break;
//				}
//		}
//		if (!flag)
//			return false;
//		if (sign == -1)
//			return !res;
//		return res;
//	}
//	bool operator==(const bigint &x) const {
//		bigint a = (*this);
//		bigint b = x;
//		a.normalize();
//		b.normalize();
//		if (a.sign == b.sign and a.num.size() == b.num.size()) {
//			bool res = true;
//			for (int i = 0; i < a.num.size() and res; i++)
//				if (a.num[i] != b.num[i])
//					res = false;
//			return res;
//		}
//		else
//			return false;
//	}
//	bool operator<=(const bigint &x) const {
//		return (((*this) < x) or ((*this) == x));
//	}
//	bool operator>(const bigint &x) const {
//		return (!((*this) <= x));
//	}
//	bool operator>=(const bigint &x) const {
//		return (!((*this) < x));
//	}
//	bool operator!=(const bigint &x) const {
//		return (!((*this) == x));
//	}
//	friend bigint max(bigint &x, bigint &y) {
//		return (x > y? x: y);
//	}
//	friend bigint min(bigint &x, bigint &y) {
//		return (x < y? x: y);
//	}
// 
//	//math operators
//	bigint operator+(const bigint &x) const {
//		if (sign == x.sign) {
//			bigint res;
//			res.sign = sign;
//			for (int i = 0; i < max(x.num.size(), num.size()); i++) {
//				int t = (i >= num.size()? 0: num[i]) + (i >= x.num.size()? 0: x.num[i]);
//				res.num.push_back(t);
//			}
//			res.normalize();
//			return res;
//		}
//		if (sign == -1)
//			return x - abs(*this);
//		else
//			return (*this) - abs(x);
//	}
//	bigint operator-(const bigint &x) const {
//		if (sign == x.sign) {
//			bigint res, a = abs(*this), b = abs(x);
//			a.clr();
//			b.clr();
//			if (a == b) {
//				res = 0;
//				return res;
//			}
//			if (b < a) {
//				for (int i = 0; i < a.num.size(); i++) {
//					int t = a.num[i] - (i >= b.num.size()? 0: b.num[i]);
//					res.num.push_back(t);
//				}
//				res.normalize();
//			}
//			else {
//				for (int i = 0; i < b.num.size(); i++) {
//					int t = b.num[i] - (i >= a.num.size()? 0: a.num[i]);
//					res.num.push_back(t);
//				}
//				res.normalize();
//				res.sign *= -1;
//			}
//			if (sign == -1)
//				res.sign *= -1;
//			return res;
//		}
//		if (sign == -1) {
//			bigint res = abs(*this) + x;
//			res.sign *= -1;
//			return res;
//		}
//		else
//			return (*this) + abs(x);
//	}
//	void operator+=(const bigint &x) {
//		(*this) = (*this) + x;
//	}
//	void operator-=(const bigint &x) {
//		(*this) = (*this) - x;
//	}
//	void operator++() {
//		(*this) += 1;
//	}
//	bigint operator++(int) {
//		bigint res;
//		++(*this);
//		return res;
//	}
//	void operator--() {
//		(*this) -= 1;
//	}
//	bigint operator--(int) {
//		bigint res;
//		--(*this);
//		return res;
//	}
//	bigint operator*(const bigint &x) const {
//		bigint res;
//		bigint a = (*this), b = x;
//		if (a.isZero() or b.isZero())
//			return 0;
//		a.clr();
//		b.clr();
//		for (int i = 0; i < b.num.size(); i++) {
//			bigint t;
//			for (int j = 1; j <= i; j++)
//				t.num.push_back(0);
//			for (int j = 0; j < a.num.size(); j++)
//				t.num.push_back(a.num[j] * b.num[i]);
//			t.normalize();
//			res += t;
//		}
//		res.normalize();
//		res.sign = a.sign * b.sign;
//		return res;
//	}
//	void operator*=(const bigint &x) {
//		(*this) = (*this) * x;
//	}
//	friend pair<bigint, bigint> dmod(const bigint &x, const bigint &y) {
//		bigint res, a = abs(x), b = abs(y), carry;
//		res.sign = y.sign * x.sign;
//		a.clr();
//		b.clr();
//		if (b.isZero())
//			return {-1, -1};
//		if (a < b) {
//			return {0, x};
//		}
//		int cnt = a.num.size() - 1;
//		for (int i = a.num.size() - 1; carry < b; i--) {
//			carry.num.push_front(a.num[i]);
//			cnt = i - 1;
//		}
//		for (int i = 1; i <= 10; i++) {
//			bigint t = b * i;
//			if (t > carry) {
//				res.num.push_front(i - 1);
//				t -= b;
//				carry -= t;
//				break;
//			}
//		}
//		for (int i = cnt; i >= 0; i--) {
//			carry.num.push_front(a.num[i]);
//			carry.normalize();
//			if (carry >= b) {
//				for (int j = 1; j <= 10; j++) {
//					bigint t = b * j;
//					if (t > carry) {
//						res.num.push_front(j - 1);
//						t -= b;
//						carry -= t;
//						break;
//					}
//				}
//			}
//			else {
//				res.num.push_front(0);
//			}
//		}
//		res.normalize();
//		if (res.sign == -1)
//			carry = y - x;
//		return {res, carry};
// 
//	}
//	bigint operator/(const bigint &x) const {
//		pair<bigint, bigint> res = dmod((*this), x);
//		return res.first;
//	}
//	void operator/=(const bigint &x) {
//		(*this) = (*this) / x;
//	}
//	bigint operator%(const bigint &x) const {
//		pair<bigint, bigint> res = dmod((*this), x);
//		return res.second;
//	}
//	void operator%=(const bigint &x) {
//		(*this) = (*this) % x;
//	}
//	friend bigint pow(const bigint &x, const bigint &y) {
//		bigint tmp = y;
//		if (tmp.isZero())
//			return 1;
//		bigint res = 1, t = y, a = x;
//	       	pair<bigint, bigint> dm;
//		while (t > 0) {
//			if ((t % 2) == 1)
//				res = res * a;
//			a *= a;
//			t /= 2;
//		}
//		return res;
//	}
//	friend bigint gcd(bigint x, bigint y) {
//		return (y.isZero()? x: gcd(y, x % y));
//	}
//	friend bigint lcm(const bigint &x, const bigint &y) {
//		return (x * y) / gcd(x, y);
//	}
//	friend bigint sqrt(const bigint &x) {
//		if (x.sign == -1)
//			return -1;
//		bigint carry, res, lef;
//		deque<pair<int, int>> t;
//		for (int i = 0; i < x.num.size(); i += 2) {
//			if (i + 1 == x.num.size())
//				t.push_front({x.num[i], 1});
//			else
//				t.push_front({x.num[i] + x.num[i + 1] * 10, 2});
//		}
//		for (int i = 0; i < t.size(); i++) {
//			if (t[i].second == 1)
//				carry.num.push_front(t[i].first);
//			else
//				carry.num.push_front(t[i].first / 10), carry.num.push_front(t[i].first % 10);
//			carry.normalize();
//			lef.num.push_front(0);
//			for (int i = 1; i <= 10; i++) {
//				lef.num[0] = i;
//				bigint tmp = (lef) * i;
//				if (tmp > carry) {
//					lef.num[0] = i - 1;
//					tmp = lef * (i - 1);
//					carry -= tmp;
//					lef += (i - 1);
//					res.num.push_front(i - 1);
//					break;
//				}
//			}
//		}
//		res.normalize();
//		return res;
//	}
// 
//	//string to bigint and bigint to string
//	void toBig(string &s) {
//		if (s[0] == '-') {
//			sign = -1;
//			s = s.substr(1);
//		}
//		else
//			sign = 1;
//		reverse(s.begin(), s.end());
//		num.clear();
//		for (int i = (s[0] == '-'); i < s.size(); i += Dig / 10) {
//			string sp;
//			for (int j = i; j < i + (Dig / 10); j++)
//				sp += s[j];
//			long long t = stol(sp);
//			num.push_back(t);
//		}
//	}
//	friend string to_string(const bigint &x) {
//		string res;
//		if (x.num.empty()) {
//			res += '0';
//			return res;
//		}
//		if (x.sign == -1)
//			res += '-';
//		for (int i = x.num.size() - 1; i >= 0; i--) {
//			string t = to_string(x.num[i]);
//			reverse(t.begin(), t.end());
//			res += t;
//		}
//		return res;
//	}
//	//change base
//	friend bigint change_base(const bigint &a, const int y, const int x) {
//		if (y == x)
//			return a;
//		bigint res, t = change_base_rev(a, y, 10);
//		t.normalize();
//		while (t > 0) {
//			res.num.push_back(BtoI(t % x));
//			t /= x;
//		}
//		return res;
//	}
//	friend bigint change_base_rev(const bigint &a, const int y, const int x) {
//		if (y == x)
//			return a;
//		if (x == 10) {
//			bigint res, t = 1, b = a;
//			b.clr();
//			for (int i = 0; i < b.num.size(); i++)
//				res += t * b.num[i], t *= y;
//			return res;
//		}
//		bigint t = change_base_rev(a, y, 10);
//		return change_base(t, 10, x);
// 
//	}
//	friend bigint CB(const bigint &a, int y, int x) {
//		if (x > y)
//			return change_base_rev(a, y, x);
//		return change_base(a, y, x);
//	}
// 
//	//bitwise operator
//	bigint operator^(const bigint &x) const {
//		bigint res, a = change_base(*this, 10, 2), b = change_base(x, 10, 2);
//		for (int i = 0; i < max(a.num.size(), b.num.size()); i++) {
//			int d1 = 0, d2 = 0;
//			if (i < a.num.size())
//				d1 = a.num[i];
//			if (i < b.num.size())
//				d2 = b.num[i];
//			res.num.push_back(d1 ^ d2);
//		}
//		res.clr();
//		res = change_base_rev(res, 2, 10);
//		res.normalize();
//		return res;
//	}
//	bigint operator&(const bigint &x) const {
//		bigint res, a = change_base(*this, 10, 2), b = change_base(x, 10, 2);
//		for (int i = 0; i < max(a.num.size(), b.num.size()); i++) {
//			int d1 = 0, d2 = 0;
//			if (i < a.num.size())
//				d1 = a.num[i];
//			if (i < b.num.size())
//				d2 = b.num[i];
//			res.num.push_back(d1 & d2);
//		}
//		res.clr();
//		res = change_base_rev(res, 2, 10);
//		res.normalize();
//		return res;
//	}
//	bigint operator|(const bigint &x) const {
//		bigint res, a = change_base(*this, 10, 2), b = change_base(x, 10, 2);
//		for (int i = 0; i < max(a.num.size(), b.num.size()); i++) {
//			int d1 = 0, d2 = 0;
//			if (i < a.num.size())
//				d1 = a.num[i];
//			if (i < b.num.size())
//				d2 = b.num[i];
//			res.num.push_back(d1 | d2);
//		}
//		res.clr();
//		res = change_base_rev(res, 2, 10);
//		res.normalize();
//		return res;
//	}
//	void operator^=(const bigint &x) {
//		(*this) = (*this) ^ x;
//	}
//	void operator&=(const bigint &x) {
//		(*this) = (*this) & x;
//	}
//	void operator|=(const bigint &x) {
//		(*this) = (*this) | x;
//	}
//	bigint operator<<(const bigint &x) {
//		bigint res = change_base((*this), 10, 2);
//		for (bigint i = 0; i < x; i++)
//			res.num.push_front(0);
//		res = change_base_rev(res, 2, 10);
//		res.normalize();
//		return res;
//	}
//	bigint operator>>(const bigint &x) {
//		bigint res = change_base((*this), 10, 2);
//		bigint t = (int)res.num.size();
//		for (bigint i = 0; i < min(x, t); i++)
//			res.num.pop_front();
//		res = change_base_rev(res, 2, 10);
//		res.normalize();
//		return res;
// 
//	}
//	void operator>>=(const bigint &x) {
//		(*this) = (*this) >> x;
//	}
//	void operator<<=(const bigint &x) {
//		(*this) = (*this) << x;
//	}
// 
//	//builtin fuctions
//	int popcount() {
//		int res = 0;
//		bigint tmp = *this;
//		tmp = CB(tmp, 10, 2);
//		for (auto i : tmp.num)
//			res += i;
//		return res;
//	}
//	int ctz() {
//		bigint tmp = *this;
//		tmp = CB(tmp, 10, 2);
//		for (int i = 0; i < tmp.num.size(); i++)
//			if (tmp.num[i])
//				return i;
//                return 1;
// 
//	}
// 
//	//cin and cout
//	friend istream& operator>>(istream &stream, bigint &x) {
//		string s;
//		stream >> s;
//		x.toBig(s);
//		x.normalize();
//		return stream;
//	}
//	friend ostream& operator<<(ostream &stream, bigint &x) {
//		if (x.num.empty()) {
//			stream << 0;
//			return stream;
//		}
//		if (!x.num.empty() and x.sign == -1)
//			stream << '-';
//		stream << (x.num.empty() ? 0 : x.num.back());
//		for (int i = (int) x.num.size() - 2; i >= 0; i--)
//			stream  << x.num[i];
//		return stream;
//	}
// 
//};
// 
////tutorial :
////everything is similar to using int exept a few functions
////BtoI(bigint x) : returns x to int (becareful with overflow)
////CB(bigint x, int a, int b) : get a bigint in base a and returns a bigint in base b (a, b <= 10)
////x.popcount() : returns number of 1 in binary form of x
////x.ctz() : returns number of 0 before the rightmost 1 in binary form of x

typedef struct vector<int> bigint; 

bigint operator + (bigint a, bigint b) { 
	int len = max(a.size(), b.size()); 
	
	a.resize(len, 0); 
	b.resize(len, 0); 
	
	bigint res(len + 1, 0);
	
	int carry = 0; 
	fori(i, 0, len - 1) { 
		res[i] = a[i] + b[i] + carry; 
		
		if(res[i] >= 10) { 
			res[i] -= 10; 
			carry = 1; 
		}
		
		else  { 
			carry = 0; 
		}
	}
	
	if(res.back() == 0 and res.size() >= 2) res.pop_back(); 
	
	return res; 
}

string tos(bigint a) { 
	int len = a.size(); 
	
	string res; 
	
	fori(i, 0, len - 1) { 
		res.push_back(char(a[i] + '0')); 
	}
	return res; 
}

bigint pw[505]; 

void solve() {
	int n, k; 
	cin >> n >> k; 
	pw[0] = vi(1, 1); 
	fori(i,1, n) { 
		pw[i] = pw[i - 1] + pw[i - 1];  
	}
	
	cout << min(9, n - 1) << endl;
	
	fori(bit, 0, min(n - 2, 8) ) {
		cout << "A=(";  
		bigint sum1 = vi(1, 0), sum0 = vi(1, 0); 
		fori(i, 0, n - 1) { 
			if(i / (1 << bit) & 1) { 
				sum1 = sum1 + pw[i]; 
			}
			else { 
				sum0 = sum0 + pw[i]; 
			}
		}
		cout << "(A&" << tos(sum0) << ")+((A&" << tos(sum1) << ")>>" << (1 << bit) << ")"; 
		cout << ")" << endl; 
	}
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 15
• Subtask 3: 0 / 35
• Subtask 4: 0 / 45