Japan Alumni Group Summer Camp 2013 Warming Up

Submission #103065

Source codeソースコード

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>

using namespace std;

#define FOR(i, a, n) for(int i = (a); i < (n); i++)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, n) for(int i = (n) - 1; i >= (a); i--)
#define RREP(i, n) RFOR(i, 0, n)
#define ALL(v) (v).begin(), (v).end()
#define fst first
#define snd second

typedef long long ll;
typedef pair<int, int> pii;

const int MAX_N = 110000;
const int MAX_V = (1 << 21) + 10;
const int MAX_LOG_V = 21;

int n;
ll a[MAX_N], s[MAX_N];
int pos[MAX_V];
bool exist[MAX_V];

void solve(){
  int v = 0;
  int mask = 0;
  RREP(i, MAX_LOG_V){
	memset(exist, false, sizeof(exist));
	mask |= (1 << i);
	REP(j, n + 1){
	  exist[s[j] & mask] = true;
	}
	bool ok = false;
	REP(j, n + 1){
	  if(exist[mask & (s[j] ^ (v | (1 << i)))]){
		ok = true;
		break;
	  }
	}
	if(ok) v |= (1 << i);
  }

  if(v == 0){
	cout << 0 << ' ' << 1 << ' ' << 1 << endl;
	return;
  }
  
  memset(pos, -1, sizeof(pos));
  REP(i, n + 1){
	if(pos[s[i]] == -1 || pos[s[i]] > i){
	  pos[s[i]] = i;
	}
  }

  pii p = pii(-1, -1);
  REP(i, n + 1){
	int ti = i;
	int tj = pos[v ^ s[i]];
	if(tj == -1) continue;
	if(ti > tj) swap(ti, tj);
	pii q = pii(ti, tj);
	if(p.fst == -1 || p > q){
	  p = q;
	}
  }
  cout << v << ' ' << p.fst + 1 << ' ' << p.snd << endl;
  return;
}

int main(){
  cin >> n;
  REP(i, n){
	cin >> a[i];
	s[i + 1] = s[i] ^ a[i];
  }
  solve();
  return 0;
}

Submission

Task問題 F - Maximum Segment XOR
User nameユーザ名 020_mitaki28
Created time投稿日時
Language言語 C++ (GCC 4.4.7)
Status状態 AC
Score得点 100
Source lengthソースコード長 1520 Byte
File nameファイル名
Exec time実行時間 118 ms
Memory usageメモリ使用量 12580 KB

Test case

Set

Set name Score得点 / Max score Cases
All 100 / 100 1,10,11,12,13,14,15,16,17,18,19,2,20,21,22,23,24,25,26,27,28,29,3,30,31,4,5,6,7,8,9

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
1 AC 53 ms 11036 KB
10 AC 57 ms 10988 KB
11 AC 55 ms 11044 KB
12 AC 47 ms 11028 KB
13 AC 52 ms 11048 KB
14 AC 52 ms 11168 KB
15 AC 60 ms 11172 KB
16 AC 87 ms 11808 KB
17 AC 75 ms 11428 KB
18 AC 111 ms 12580 KB
19 AC 53 ms 11048 KB
2 AC 46 ms 11036 KB
20 AC 52 ms 11040 KB
21 AC 46 ms 11052 KB
22 AC 48 ms 10996 KB
23 AC 53 ms 11048 KB
24 AC 53 ms 11044 KB
25 AC 49 ms 11052 KB
26 AC 49 ms 11040 KB
27 AC 53 ms 11172 KB
28 AC 94 ms 12068 KB
29 AC 105 ms 12204 KB
3 AC 54 ms 11000 KB
30 AC 86 ms 11688 KB
31 AC 118 ms 12580 KB
4 AC 35 ms 2784 KB
5 AC 53 ms 11044 KB
6 AC 53 ms 11056 KB
7 AC 53 ms 11048 KB
8 AC 47 ms 10996 KB
9 AC 53 ms 11052 KB