Submission #734570

#	Time	Username	Problem	Language	Result	Execution time	Memory
734570		keta_tsimakuridze	XOR Sum (info1cup17_xorsum)	C++14	77 / 100	965 ms	21772 KiB

xorsum

#include<bits/stdc++.h>
#define f first
#define s second
#define pii pair<int,int>
using namespace std;
const int mod = 1e9 + 7; // !
int t;
vector<int> x;
main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int a;
        cin >> a;
        x.push_back(a);
    }
//    vector<int> cn(30);
//    for(int i = 0; i < n; i++) {
//        for(int j = i; j < n; j++) {
//            for(int k = 0; k < 30; k++)
//            if((x[i] + x[j]) & (1 << k)) cn[k] += 1;
//        }
//    }
    int ans = 0;
    for(int i = 0; i <= 28; i++) {
        vector<int> xn;
        for(int j = 0; j < x.size(); j++) {
            if(x[j] & (1 << i)) continue;
            xn.push_back(x[j]);
        }
        for(int j = 0; j < x.size(); j++) {
            if(x[j] & (1 << i)) xn.push_back(x[j]);
        }
        x = xn;
        vector<int> v = {(1 << i) + (1 << (i + 1)),  1 << (i + 1), 1 << (i)};
        vector<int> r(3);
        r[0] = r[1] = r[2] = n;
        int c = 0, M = (1ll << (i + 1)) - 1;
        for(int j = 0; j < x.size(); j++) {
            //    cout << x[j] << " ";
            for(int t = 0; t < 3; t++) {
                while(r[t] > 0 && (x[r[t] - 1] & M) + (x[j] & M) >= v[t]) --r[t];
            }
            c += n - max(j, r[0]) + max(j, r[1]) - max(j, r[2]); // cout << c << endl;
        }
//        cout << i << " _ " << c << " " << cn[i] << endl;
        if(c % 2) ans += 1 << i;
    }
    cout << ans;
 }

Compilation message (stderr)

xorsum.cpp:9:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    9 | main(){
      | ^~~~
xorsum.cpp: In function 'int main()':
xorsum.cpp:28:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for(int j = 0; j < x.size(); j++) {
      |                        ~~^~~~~~~~~~
xorsum.cpp:32:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |         for(int j = 0; j < x.size(); j++) {
      |                        ~~^~~~~~~~~~
xorsum.cpp:40:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |         for(int j = 0; j < x.size(); j++) {
      |                        ~~^~~~~~~~~~

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