oj.uz

Submission #734571

# Submission time Handle Problem Language Result Execution time Memory
734571 2023-05-02T16:26:40 Z keta_tsimakuridze XOR Sum (info1cup17_xorsum) C++14
100 / 100
 1004 ms 12484 KB 
#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 <= 29; 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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 5 ms 340 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 637 ms 12304 KB Output is correct
2 Correct 532 ms 11816 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 637 ms 12304 KB Output is correct
2 Correct 532 ms 11816 KB Output is correct
3 Correct 727 ms 12424 KB Output is correct
4 Correct 688 ms 12020 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 105 ms 1644 KB Output is correct
4 Correct 106 ms 1636 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 340 KB Output is correct
2 Correct 5 ms 340 KB Output is correct
3 Correct 637 ms 12304 KB Output is correct
4 Correct 532 ms 11816 KB Output is correct
5 Correct 727 ms 12424 KB Output is correct
6 Correct 688 ms 12020 KB Output is correct
7 Correct 105 ms 1644 KB Output is correct
8 Correct 106 ms 1636 KB Output is correct
9 Correct 1004 ms 12344 KB Output is correct
10 Correct 1002 ms 12260 KB Output is correct
11 Correct 972 ms 12484 KB Output is correct