Submission #1146517

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146517		ReLice	XOR Sum (info1cup17_xorsum)	C++20	0 / 100	370 ms	23876 KiB

xorsum

#include <bits/stdc++.h>
#define ll long long
#define ld double
#define pb push_back
#define pf push_front
#define ins insert
#define fr first
#define sc second
#define endl "\n"
#define all(x) x.begin(), x.end()

using namespace std;
void fre(string& name){freopen((name + ".in").c_str(), "r", stdin);freopen((name + ".out").c_str(), "w", stdout);}
void start(){ios_base::sync_with_stdio(NULL);cin.tie(nullptr);cout.tie(nullptr);}

const ll N = 2e5 + 5;
const ll inf = 1e9;
const ll mod = 1e9 + 7;

void solve() {
    ll i;
    
    ll n;
    cin>>n;
    
    vector<ll> v(n), c(n), lst(n);
    ll cnt[2][2][2][31];
    
    for(i=0;i<n;i++)  cin>>v[i];
    ll ans = 0;
    
    for(ll bit = 0;bit<=30;bit++){
		memset(cnt, 0, sizeof(cnt));
		
		for(i=0;i<n;i++){
			ll a = (1 & (v[i]>>bit));
			ll b = 0;
			if(bit) b = (1 & (v[i]>>(bit - 1)));
			if(bit > 1){
				if(1 & (v[i]>>(bit - 2))) {
					c[i]++;
					lst[i] = 1;
				}
				else{
					c[i] = 0;
					lst[i]++;
				}
			}
			
			cnt[a][b][1][c[i]]++;
			cnt[a][b][0][lst[i]]++;
		}
		
		for(i=29;i>=0;i--){
			for(auto a : {0, 1}){
				for(auto b : {0, 1}){
					cnt[a][b][1][i] += cnt[a][b][1][i + 1];
				}
			}
		}
		
		for(i=1;i<=30;i++){
			for(auto a : {0, 1}){
				for(auto b : {0, 1}){
					cnt[a][b][0][i] += cnt[a][b][0][i - 1];
				}
			}
		}
		
		
		ll sum = 0, x = 0;
		
		for(i=0;i<n;i++){
			ll a = (1 & (v[i]>>bit));
			ll b = 0;
			if(bit) b = (1 & (v[i]>>(bit - 1)));
			
			auto zero = [&](ll x, ll y){
				ll sum = 0;
				if(bit < 2) sum += cnt[x][y][0][30];
				else{
					if(1 & (v[i] >> (bit - 2))){
						sum += cnt[x][y][0][30] - cnt[x][y][0][c[i]];
					}
					else {
						sum += cnt[x][y][1][0] - cnt[x][y][1][lst[i]];
					}
				}
				return sum;
			};
			
			auto one = [&](ll x, ll y){
				ll sum = 0;
				if(bit < 2) return cnt[x][y][0][30];
				else{
					if(1 & (v[i] >> (bit - 2))){
						sum += cnt[x][y][0][c[i]];
					}
					else{
						sum += cnt[x][y][1][lst[i]];
					}
				}
				return sum;
			};
			
			if(a + b == 2){
				sum += cnt[1][1][0][30] + zero(0, 0);
				x++;
			}
			if(a == 1 && b == 0){
				sum += cnt[0][0][0][30] + zero(0, 1);
			}
			if(a == 0 && b == 1){
				sum += cnt[0][1][0][30] + zero(1, 0) + one(0, 0);
				x++;
			}
			if(a + b == 0){
				sum += cnt[1][0][0][30] + zero(1, 1) + one(0, 1);
			}
		}
		
		sum -= (sum - x) / 2;
		
		cout<<bit<<' '<<sum<<endl;
		
		if(sum % 2) ans += (1<<bit);
	}
	
	cout<<ans<<endl;
}

signed main(){
    start();

    ll t = 1;
    //cin>>t;

    while(t--) solve();
}
/*



*/

Compilation message (stderr)

xorsum.cpp: In function 'void fre(std::string&)':
xorsum.cpp:13:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | void fre(string& name){freopen((name + ".in").c_str(), "r", stdin);freopen((name + ".out").c_str(), "w", stdout);}
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
xorsum.cpp:13:75: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | void fre(string& name){freopen((name + ".in").c_str(), "r", stdin);freopen((name + ".out").c_str(), "w", stdout);}
      |                                                                    ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 11
• Subtask 3: 0 / 21
• Subtask 4: 0 / 38
• Subtask 5: 0 / 23