Submission #3183143

---

Source Code Expand

// ~/BAU/ACM-ICPC/Teams/Rampage/Corvus
// ~/sudo apt-get verdict Accpeted

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <memory.h>
#include <limits.h>
#include <math.h>
#include <string.h>
#include <string>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <functional>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
const int N = 205;
const ll MOD = 1e9 + 7;
const double eps = 1e-9;

struct cmp {
	bool operator()(const vector<ll> &a, const vector<ll> &b) const {
		for (int i = 1; i < a.size(); i++) {
			if (a[i] - a[i - 1] != b[i] - b[i - 1])
				return a[i] - a[i - 1] < b[i] - b[i - 1];
		}
		return false;
	}
};

int n;
ll k, a[N];
map<vector<ll>, vector<pair<ll, ll> >, cmp> mp;

inline int count(ll x) {
	int c = 0;
	while (x) {
		c++;
		x -= (x & -x);
	}
	return c;
}

vector<ll> calcDiff(vector<ll> &v) {
	vector<ll> r;
	for (int i = 1; i < v.size(); i++)
		r.push_back(v[i] - v[i - 1]);
	return r;
}

int main() {
	scanf("%d%lld", &n, &k);
	for (int i = 0; i < n; i++)
		scanf("%lld", a + i);
	for (ll d = 0; d <= min(60ll, k); d++) {
		ll msk = (1ll << d) - 1;
		vector<ll> v;
		v.push_back(-1);
		for (int i = 0; i < n; i++)
			v.push_back(a[i] & msk);
		sort(v.begin(), v.end());
		v.resize(unique(v.begin(), v.end()) - v.begin());
		for (int i = 1; i < (int)v.size(); i++) {
			ll pre = v[i - 1] + 1, cur = v[i], val = pre;
			for(ll j=60; j>=0; j--)
				if (pre >> j != cur >> j) {
					if (pre >> j << j == pre) val = pre;
					else val = cur >> j << j;
					break;
				}
			ll rem = k - d - count(val);
			if (rem < 0) continue;
			vector<ll> v2;
			for (int j = 0; j < n; j++)
				v2.push_back((a[j] - val) >> d);
			if (v2[0] < 0) continue;
			mp[v2].push_back(make_pair(max(0ll,v2[0]-rem), v2[0]));
		}
	}
	int ans = 0;
	for (auto it = mp.begin(); it != mp.end(); it++) {
		vector<pair<ll, ll> > v = it->second;
		sort(v.begin(), v.end());
		ll last = v[0].first - 1;
		for (int i = 0; i < (int)v.size(); i++) {
			ll l = max(last + 1, v[i].first), r = v[i].second;
			if (l <= r)
				ans = (ans + (r - l + 1)) % MOD;
			last = max(last, r);
		}
	}
	printf("%d\n", ans);
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:65:25: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%lld", &n, &k);
                         ^
./Main.cpp:67:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld", a + i);
                       ^

Judge Result