# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
338376 | Trickster | XOR (IZhO12_xor) | C++14 | 69 ms | 147180 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//Suleyman Atayew
#include <algorithm>
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cmath>
#include <map>
#include <set>
#define N 7500010
#define ff first
#define ss second
#define pb push_back
#define ll long long
#define mod 1000000007
#define pii pair <int, int>
#define sz(a) (int)(a.size())
ll bigmod(ll a, ll b) { if(b==0)return 1; ll ret = bigmod(a, b/2); return ret * ret % mod * (b%2 ? a : 1) % mod; }
using namespace std;
int v[N];
int In[N];
int F[N][5];
int sz, nd, n, k;
void upd(int x, int y)
{
int nd = 0;
for(int i = 0; i <= 30; i++) {
int tp = 0;
if(((1<<i) & x)) tp = 1;
if(F[nd][tp] == -1) F[nd][tp] = ++sz;
nd = F[nd][tp];
In[nd] = min(y, In[nd]);
}
}
int tap(int x, int y, int need, int nd)
{
int tp = 1;
if((1<<y)&x) tp = 0;
if(need <= 0) return In[nd];
if((1<<y) < need) {
if(F[nd][tp] == -1) return 1e9;
return tap(x, y+1, need - (1<<y), F[nd][tp]);
}
if(F[nd][0] == -1 && F[nd][1] == -1) return 1e9;
if(F[nd][0] == -1) {
need -= (tp == 0 ? 0 : (1<<y));
return tap(x, y+1, need, F[nd][1]);
}
if(F[nd][1] == -1) {
need -= (tp == 1 ? 0 : (1<<y));
return tap(x, y+1, need, F[nd][0]);
}
return min(tap(x, y+1, (need - (tp == 0 ? (1<<y) : 0)), F[nd][0]), tap(x, y+1, (need - (tp == 1 ? (1<<y) : 0)), F[nd][1]));
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> k;
for(int i = 1; i <= 7500000; i++) F[i][0] = F[i][1] = -1, In[nd] = 1e9;
for(int i = 1; i <= n; i++)
cin >> v[i], v[i] ^= v[i-1];
int l = 1e9, ans = 0;
for(int i = 1; i <= n; i++) {
int now = tap(v[i], 0, k, 0);
upd(v[i], i);
// cout << i << " " << now << " " << v[i] << "\n";
if(ans < i - now) {
ans = i - now;
l = now+1;
}
}
if(l == 1e9) l = 1, ans = 1;
cout << l << " " << ans;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |