oj.uz

Submission #67967

# Submission time Handle Problem Language Result Execution time Memory
67967 2018-08-15T15:56:43 Z MrTEK XOR Sum (info1cup17_xorsum) C++14
77 / 100
 1600 ms 24908 KB 
#include <bits/stdc++.h>

using namespace std;
#define mp make_pair
#define pb push_back
#define len(a) (int)a.size()
#define fi first
#define sc second
#define left ind + ind
#define right ind + ind + 1
#define pw(n) (1 << (n))
#define mid (l + r) / 2 
#define d1(w) cerr<<#w<<":"<<w<<endl;
#define d2(w,c) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<endl;
#define d3(w,c,z) cerr<<#w<<":"<<w<<" "<<#c<<":"<<c<<" "<<#z<<":"<<z<<endl;
#define FAST_IO ios_base::sync_with_stdio(false);
#define endl '\n'

const int maxn = 620;
const long long LINF = 1e18;
const int LOG = 31;
const int INF = 1e9 + 5;
const int N = 1e6 + 5;
const int M = 4e3 + 5;
const int SQ = 350;
const int MOD = 998244353;

typedef pair <int,int> pii;

int n,a[N],mark[N],ans;

pii b[N],nb[N];

int main() {

	scanf("%d",&n);

	for (int i = 1 ; i <= n ; i++) {
		scanf("%d",&a[i]);
		b[i] = mp(a[i] & 1,i);
	}

	sort(b + 1, b + n + 1);
	b[n + 1] = mp(INF,0);

	memset(mark,-1,sizeof mark);

	for (int i = 0 ; i < LOG ; i++) {
		long long cnt = 0;
		int r1 = n + 1,r2 = n + 1,r3 = n + 1;
		for (int l = 1 ; l <= n ; l++) {
			while(r3 > 1 && b[l].fi + b[r3 - 1].fi >= pw(i + 1) + pw(i)) r3--;
			r2 = min(r3,r2);
			while(r2 > 1 && b[l].fi + b[r2 - 1].fi >= pw(i + 1)) r2--;
			r1 = min(r2,r1);
			while(r1 > 1 && b[l].fi + b[r1 - 1].fi >= pw(i)) r1--;
			cnt += max(0,n - r1 - (r3 - r2) + 1);
		}
		int say = 0;
		for (int j = 1 ; j <= n ; j++) if ((b[j].fi * 2) & pw(i)) say++;
		cnt = (cnt + say) / 2;
		if (cnt & 1) ans += pw(i);
		if (i < LOG - 1) {
			int last = 0;
			for (int j = 1 ; j <= n ; j++) {
				if (a[b[j].sc] & pw(i + 1)) mark[j] = i;
				else nb[++last] = b[j]; 
			}
			for (int j = 1 ; j <= n ; j++) if(mark[j] == i) nb[++last] = mp(b[j].fi + pw(i + 1),b[j].sc);
			for (int j = 1 ; j <= n ; j++) b[j] = nb[j];
		}		
	}

	printf("%d\n",ans);

	return 0;
}

Compilation message

xorsum.cpp: In function 'int main()':
xorsum.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
xorsum.cpp:39:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
   ~~~~~^~~~~~~~~~~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4344 KB Output is correct
2 Correct 11 ms 4456 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 965 ms 23856 KB Output is correct
2 Correct 993 ms 23856 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 965 ms 23856 KB Output is correct
2 Correct 993 ms 23856 KB Output is correct
3 Correct 1271 ms 24128 KB Output is correct
4 Correct 1155 ms 24128 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4344 KB Output is correct
2 Correct 11 ms 4456 KB Output is correct
3 Correct 164 ms 24128 KB Output is correct
4 Correct 141 ms 24128 KB Output is correct

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 4344 KB Output is correct
2 Correct 11 ms 4456 KB Output is correct
3 Correct 965 ms 23856 KB Output is correct
4 Correct 993 ms 23856 KB Output is correct
5 Correct 1271 ms 24128 KB Output is correct
6 Correct 1155 ms 24128 KB Output is correct
7 Correct 164 ms 24128 KB Output is correct
8 Correct 141 ms 24128 KB Output is correct
9 Correct 1544 ms 24192 KB Output is correct
10 Execution timed out 1671 ms 24908 KB Time limit exceeded
11 Halted 0 ms 0 KB -