oj.uz

Submission #648259

# Submission time Handle Problem Language Result Execution time Memory
648259 2022-10-05T20:32:44 Z kingfran1907 Popcount (COCI19_popcount) C++14
110 / 110
 5 ms 340 KB 
#include <bits/stdc++.h>
#define X first
#define Y second

using namespace std;
typedef long long llint;

const int maxn = 510;
const int base = 31337;
const int mod = 1e9+7;
const int inf = 0x3f3f3f3f;
const int logo = 20;
const int off = 1 << logo;
const int treesiz = off << 1;

int n, k;
vector< string > sol;
string pot[maxn];

string add(string a, string b) {
	while (a.size() < b.size()) a.push_back('0');
	while (b.size() < a.size()) b.push_back('0');

	int car = 0;
	string out;
	for (int i = 0; i < a.size(); i++) {
		int tren = (int)a[i] + b[i] - 2 * '0' + car;
		out.push_back((tren % 10) + '0');
		car = tren / 10;
	}
	if (car > 0) out.push_back(car + '0');
	while (out.back() == '0') out.pop_back();
	return out;
}

string conv(int x) {
	if (x == 0) return "0";
	string out;
	while (x > 0) {
		out.push_back((x % 10) + '0');
		x /= 10;
	}
	reverse(out.begin(), out.end());
	return out;
}

int main() {
	scanf("%d%d", &n, &k);
	pot[0] = "1";
	for (int i = 1; i < n; i++) 
		pot[i] = add(pot[i - 1], pot[i - 1]);

	for (int i = 1; i < n; i *= 2) {
		string num = "0";
		string comp = "0";
		for (int j = 0; j < n; j++) {
			if (j & i) num = add(num, pot[j]);
			else comp = add(comp, pot[j]);
		}

		reverse(num.begin(), num.end());
		reverse(comp.begin(), comp.end());
		string tren = "A=((A&" + comp + ")+((A&" + num + ")>>" + conv(i) + "))";
		sol.push_back(tren);
	}

	cout << sol.size() << "\n";
	for (string tren : sol) cout << tren << "\n";
	return 0;
}

Compilation message

popcount.cpp: In function 'std::string add(std::string, std::string)':
popcount.cpp:26:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for (int i = 0; i < a.size(); i++) {
      |                  ~~^~~~~~~~~~
popcount.cpp: In function 'int main()':
popcount.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Accepted.
2 Correct 1 ms 212 KB Accepted.
3 Correct 1 ms 312 KB Accepted.
4 Correct 1 ms 212 KB Accepted.
5 Correct 1 ms 212 KB Accepted.
6 Correct 1 ms 212 KB Accepted.
7 Correct 1 ms 212 KB Accepted.
8 Correct 1 ms 212 KB Accepted.
9 Correct 1 ms 212 KB Accepted.
10 Correct 1 ms 312 KB Accepted.
11 Correct 1 ms 308 KB Accepted.
12 Correct 1 ms 212 KB Accepted.
13 Correct 1 ms 212 KB Accepted.
14 Correct 1 ms 212 KB Accepted.

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Accepted.

Subtask #3
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Accepted.
2 Correct 1 ms 316 KB Accepted.
3 Correct 1 ms 212 KB Accepted.
4 Correct 0 ms 212 KB Accepted.
5 Correct 1 ms 212 KB Accepted.
6 Correct 0 ms 212 KB Accepted.
7 Correct 0 ms 212 KB Accepted.
8 Correct 0 ms 212 KB Accepted.
9 Correct 1 ms 212 KB Accepted.
10 Correct 0 ms 212 KB Accepted.
11 Correct 0 ms 212 KB Accepted.
12 Correct 1 ms 212 KB Accepted.
13 Correct 1 ms 212 KB Accepted.
14 Correct 1 ms 212 KB Accepted.
15 Correct 1 ms 212 KB Accepted.
16 Correct 1 ms 212 KB Accepted.
17 Correct 1 ms 212 KB Accepted.
18 Correct 1 ms 212 KB Accepted.
19 Correct 1 ms 212 KB Accepted.
20 Correct 1 ms 212 KB Accepted.
21 Correct 1 ms 212 KB Accepted.

Subtask #4
45.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Accepted.
2 Correct 2 ms 340 KB Accepted.
3 Correct 3 ms 312 KB Accepted.
4 Correct 4 ms 340 KB Accepted.
5 Correct 1 ms 212 KB Accepted.
6 Correct 1 ms 212 KB Accepted.
7 Correct 1 ms 212 KB Accepted.
8 Correct 1 ms 212 KB Accepted.
9 Correct 2 ms 340 KB Accepted.
10 Correct 1 ms 340 KB Accepted.
11 Correct 2 ms 340 KB Accepted.
12 Correct 4 ms 340 KB Accepted.