Submission #1622102

---

Source Code Expand

#include <bits/stdc++.h>
 
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define li long long
#define itn int
 
using namespace std;
 
inline int nxt(){
	int n;
	scanf("%d", &n);
	return n;
}

template <typename T>
ostream& operator <<(ostream& ostr, const vector<T>& a) {
	ostr << "(";
	for (size_t i = 0; i < a.size(); ++i) {
		if (i) {
			ostr << ", ";
		}
		ostr << a[i];
	}
	ostr << ")";
	return ostr;
}

int f(int x) {
	if (x & 1) {
		return 1 << (31 - __builtin_clz(x));
	} else {
		return x >> 1;
	}
}

int get(vector<int> a) {
	int n = a.size();
	vector<int> b(n);
	vector<int> bad;
	int ans = 0;
	for (int i = 0; i < n; ++i) {
		if (__builtin_popcount(a[i]) > 1) {
			bad.push_back(i);
			b[i] = 1;
		}
		b[i] += 31 - __builtin_clz(a[i]);
	}
	ans += accumulate(all(b), 0);
	for (int i = 0; i < n - 1; ++i) {
		ans -= min(b[i], b[i + 1]);
	}

	vector<int> really_bad;
	for (int idx : bad) {
		int cnt_near_greater = 0;
		if (idx > 0 && b[idx - 1] >= b[idx]) {
			++cnt_near_greater;
		}
		if (idx < n - 1 && b[idx + 1] >= b[idx]) {
			++cnt_near_greater;
		}
		if (cnt_near_greater == 2) {
			really_bad.push_back(idx);
		}
	}

	for (int i = 0; i < (int)really_bad.size();) {
		ans += 1;
		if (i == (int)really_bad.size() - 1) {
			break;
		}
		if (really_bad[i] + 1 == really_bad[i + 1]) {
			i += 2;
		} else {
			i += 1;
		}
	}

	return ans;
}

int main() {
	int n = nxt();
	vector<int> a(n);
	for (itn i = 0; i < n; ++i) {
		a[i] = nxt();
	}

	int ans = 0;
	vector<int> b;
	for (int x : a) {
		if (x == 1) {
			ans += get(b);
			b.clear();
		} else {
			b.push_back(x);
		}
	}
	ans += get(b);

	printf("%d\n", ans);

	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int nxt()’:
./Main.cpp:12:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^

Judge Result