제출 #589513

#제출 시각아이디문제언어결과실행 시간메모리
589513TheEvilBirdXOR (IZhO12_xor)C++17
0 / 100
1 ms340 KiB
#include <iostream> #include <iomanip> #include <cassert> #include <vector> #include <numeric> #include <string> #include <bitset> #include <cmath> #include <algorithm> #include <stack> #include <queue> #include <deque> #include <set> #include <unordered_set> #include <map> #include <unordered_map> #include <random> #include <ctime> #include <chrono> using namespace std; #define all(x) (x).begin(), (x).end() #define rall(x) (x).rbegin(), (x).rend() #define sz(x) (int)((x).size()) typedef unsigned int uint; typedef long long ll; typedef unsigned long long ull; //typedef __int128_t int128; typedef long double ld; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const char en = '\n'; const int INF = 1e9 + 7; const ll INFLL = 1e18; mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count()); #ifdef __APPLE__ #include "debug.h" //#define debug(...) 42 #else #define debug(...) 42 #endif const int N = 250'000; const int LOG = 30; int get_mask(int mask, int i) { return (mask & (1 << i)); } void solve() { int n, x; cin >> n >> x; vector<int> a(n); for (int i = 0; i < n; ++i) { cin >> a[i]; } vector<vector<int>> dp(n, vector<int> (LOG, -1)); for (int l = 0; l < LOG; ++l) { int last = n, cnt = 0; for (int i = n - 1; i >= 0; --i) { if (get_mask(a[i], l)) { ++cnt; } if (cnt == 0) { continue; } if (cnt == 1) { last = i; } if (cnt % 2 == 1) { dp[i][l] = n - i; } else { dp[i][l] = last - i; } } } int ans = -1, idans = -1; auto chkmx = [&](int cur, int i) { if (cur > ans) { ans = cur; idans = i + 1; } }; for (int i = 0; i < n; ++i) { int now = n - i; for (int l = LOG - 1; l >= 0; --l) { if (get_mask(x, l)) { now = min(now, dp[i][l]); } else { int cur = now; cur = min(cur, dp[i][l]); chkmx(cur, i); } } chkmx(now, i); } assert(ans != -1); cout << idans << ' ' << ans << en; } int main() { #ifdef __APPLE__ freopen("input.txt", "r", stdin); #else ios_base::sync_with_stdio(0); cin.tie(0); #endif solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...