oj.uz

Submission #390068

# Submission time Handle Problem Language Result Execution time Memory
390068 2021-04-15T09:23:21 Z rk42745417 XOR Sum (info1cup17_xorsum) C++17
100 / 100
 1525 ms 14188 KB 
/*
--------------              |   /
      |                     |  /
      |                     | /
      |             *       |/          |    |         ------            *
      |                     |           |    |        /      \
      |             |       |\          |    |       |       |\          |
   \  |             |       | \         |    |       |       | \         |
    \ |             |       |  \        |    |        \     /   \        |
     V              |       |   \        \__/|         -----     \       |
*/
#include <bits/stdc++.h>
using namespace std;

#define EmiliaMyWife ios::sync_with_stdio(0); cin.tie(NULL);
using ll = int64_t;
using ull = uint64_t;
using ld = long double;
using uint = uint32_t;
const double EPS  = 1e-8;
const int INF     = 0x3F3F3F3F;
const ll LINF     = 4611686018427387903;
const int MOD     = 1e9+7;
/*--------------------------------------------------------------------------------------*/

signed main() { EmiliaMyWife
	int n;
	cin >> n;
	vector<int> arr(n);
	for(int i = 0; i < n; i++)
		cin >> arr[i];
	
	int ans = 0;
	for(int a : arr)
		ans ^= a + a;

	for(int i = 0; i < 30; i++) {
		vector<int> owo[2];
		for(int a : arr)
			owo[a >> i & 1].push_back(a);

		int w = 0, u = 1 << i;
		for(int t = 0; t < 2; t++) {
			auto &cur = owo[t], oth = owo[!t];

			int it = cur.size();
			for(int j = 0; j < cur.size(); j++) {
				while(it && cur[it - 1] % u + cur[j] % u >= u)
					it--;
				w += cur.size() - max(it, j + 1);
			}
			//cout << "here " << i << ' ' << w << '\n';
			
			if(t)
				break;
			it = oth.size();
			for(int j = 0; j < cur.size(); j++) {
				while(it && oth[it - 1] % u + cur[j] % u >= u)
					it--;
				w += it;
			}
			//cout << "owo " << i << ' ' << w << '\n';
		}
		
		//cout << i << ' ' << w << '\n';
		if(w & 1)
			ans ^= u;

		int it = 0;
		for(auto &x : owo)
			for(int a : x)
				arr[it++] = a;
	}
	cout << ans << '\n';
}

Compilation message

xorsum.cpp: In function 'int main()':
xorsum.cpp:47:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   47 |    for(int j = 0; j < cur.size(); j++) {
      |                   ~~^~~~~~~~~~~~
xorsum.cpp:57:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |    for(int j = 0; j < cur.size(); j++) {
      |                   ~~^~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 332 KB Output is correct
2 Correct 7 ms 380 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 900 ms 13144 KB Output is correct
2 Correct 873 ms 11732 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 900 ms 13144 KB Output is correct
2 Correct 873 ms 11732 KB Output is correct
3 Correct 1123 ms 12952 KB Output is correct
4 Correct 1085 ms 12840 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 332 KB Output is correct
2 Correct 7 ms 380 KB Output is correct
3 Correct 154 ms 1896 KB Output is correct
4 Correct 158 ms 1888 KB Output is correct

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 332 KB Output is correct
2 Correct 7 ms 380 KB Output is correct
3 Correct 900 ms 13144 KB Output is correct
4 Correct 873 ms 11732 KB Output is correct
5 Correct 1123 ms 12952 KB Output is correct
6 Correct 1085 ms 12840 KB Output is correct
7 Correct 154 ms 1896 KB Output is correct
8 Correct 158 ms 1888 KB Output is correct
9 Correct 1522 ms 14188 KB Output is correct
10 Correct 1525 ms 14064 KB Output is correct
11 Correct 1525 ms 14012 KB Output is correct