Submission #674088

#	Time	Username	Problem	Language	Result	Execution time	Memory
674088		chanhchuong123	XOR (IZhO12_xor)	C++14	100 / 100	173 ms	59372 KiB

xor

#include <bits/stdc++.h>
using namespace std;
#define task "C"
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
  	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
  	if (a < b) {a = b; return true;} return false;
}

const int N = 250005;
int n, k, a[N];
pair<int, int> res;

struct Trie {
	Trie* nxt[2];
	int minID;

	Trie() {
		nxt[0] = nxt[1] = nullptr;
		minID = n + 1;
	}
} *root;

void add(int id, int x) {
	Trie *p = root;
	for (int i = 29; i >= 0; --i) {
		int LOVE = x >> i & 1;
		if (p->nxt[LOVE] == nullptr) p->nxt[LOVE] = new Trie();
		p = p->nxt[LOVE]; mini(p->minID, id);
	}
}

int query(int x) {
	Trie *p = root;
	int ans = n + 1;
	for (int i = 29; i >= 0; --i) {
		int LOVE = (x >> i & 1) ^ 1;
		if ((k >> i & 1) == 0) {
			if (p->nxt[LOVE] != nullptr) 
				mini(ans, p->nxt[LOVE]->minID);
			LOVE = LOVE ^ 1;
		}
		if (p->nxt[LOVE] == nullptr) break;
		p = p->nxt[LOVE];
	}
	return ans;
}

int main() {
  	ios_base::sync_with_stdio(0);
  	cin.tie(0); cout.tie(0);

  	if (fopen(task".inp","r")) {
    	freopen(task".inp","r",stdin);
    	freopen(task".out","w",stdout);
  	}

  	cin >> n >> k; k--;
  	if (k == -1) {
  		cout << "1 " << n;
  		return 0;
  	}
  	res.fi = -1; res.se = 0;
  	root = new Trie(); add(0, 0);
  	for (int i = 1; i <= n; ++i) {
  		cin >> a[i];
  		a[i] ^= a[i - 1];
  		int j = query(a[i]);
  		if (i - j > res.se) {
  			res.fi = j + 1;
  			res.se = i - j;
  		}
  		add(i, a[i]);
  	}	
  	cout << res.fi << ' ' << res.se;
}

Compilation message (stderr)

xor.cpp: In function 'int main()':
xor.cpp:60:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |      freopen(task".inp","r",stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
xor.cpp:61:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |      freopen(task".out","w",stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100