oj.uz

답안 #482266

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
482266 2021-10-24T00:21:37 Z urosk XOR (IZhO12_xor) C++14
100 / 100
 142 ms 46344 KB 
// __builtin_popcount(x) broj bitova
// __builtin_popcountll(x) long long
#define here cerr<<"---------------------------\n"
#include "bits/stdc++.h"
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define rall(a) a.begin(),a.end(),greater<int>()
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}
#define pi 3.14159265358979323846
using namespace std;
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

void setIO(string inoutname)
{
	freopen((inoutname+".in").c_str(),"r",stdin);
    	freopen((inoutname+".out").c_str(),"w",stdout);
}

#define maxn 250005
#define maxx 5000005
#define lg 31
ll n,x;
ll a[maxn];
ll t[maxx][2];
ll col[maxx];
ll id = 1;
void add(ll x,ll z){
    ll i = 0;
    for(ll j = lg;j>=0;j--){
        ll b = (1<<j)&x;
        if(b>0) b = 1;
        if(t[i][b]==0){
            t[i][b] = id;
            col[id] = z;
            id++;
        }
        i = t[i][b];
        col[i] = min(col[i],z);
    }
}
ll reshi(ll id){
    ll y = a[id];
    ll i = 0;
    ll ans = llinf;
    ll sum = 0;
    for(ll j = lg;j>=0;j--){
        ll b = (1<<j)&y;
        ll c = (1<<j)&x;
        if(b>0) b = 1;
        if(c>0) c = 1;
        if(c){
            if(t[i][!b]==0) break;
            i = t[i][!b];
        }else{
            if(t[i][!b]){
                ans = min({ans,col[t[i][!b]],col[t[i][!b]]});
            }
            if(t[i][b]==0) break;
            i = t[i][b];
        }
    }
    if(ans==llinf) return -1;
    return ans;
}
void tc(){
	//ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);;
    cin >> n >> x;
    for(ll i = 1;i<=n;i++){
        cin >> a[i];
        a[i] = a[i]^a[i-1];
    }
    ll len = -1;
    ll j = -1;
    x--;
    for(ll i = 1;i<=n;i++){
        if(a[i]>x){
            len = i;
            j = 1;
            add(a[i],i);
            //cerr<<1<< " "<<i<<endl;
            continue;
        }
        ll j2 = reshi(i)+1;
        //cerr<<j2<< " "<<i<<endl;
        if(j2==0){
            add(a[i],i);
            continue;
        }
        ll len2 = i-j2+1;
        if((a[i]^a[j2-1])>=x&&len2>len){
            swap(len,len2);
            swap(j,j2);
        }
        add(a[i],i);
    }
    cout<<j<< " "<<len<<endl;
}
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
	//setIO("lol");
	int t; t = 1;
	while(t--){
		tc();
	}
	return 0;
}
/*
4 6
6 1 2 4
out: 2 3
*/

Compilation message

xor.cpp: In function 'long long int reshi(long long int)':
xor.cpp:62:8: warning: unused variable 'sum' [-Wunused-variable]
   62 |     ll sum = 0;
      |        ^~~
xor.cpp: In function 'void setIO(std::string)':
xor.cpp:32:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |  freopen((inoutname+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
xor.cpp:33:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |      freopen((inoutname+".out").c_str(),"w",stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 6 ms 1612 KB Output is correct
6 Correct 8 ms 1872 KB Output is correct
7 Correct 8 ms 1868 KB Output is correct
8 Correct 9 ms 1996 KB Output is correct
9 Correct 54 ms 21640 KB Output is correct
10 Correct 44 ms 21804 KB Output is correct
11 Correct 50 ms 21800 KB Output is correct
12 Correct 44 ms 21624 KB Output is correct
13 Correct 44 ms 21772 KB Output is correct
14 Correct 45 ms 21824 KB Output is correct
15 Correct 57 ms 21704 KB Output is correct
16 Correct 49 ms 21644 KB Output is correct
17 Correct 130 ms 46204 KB Output is correct
18 Correct 142 ms 46340 KB Output is correct
19 Correct 140 ms 46344 KB Output is correct
20 Correct 137 ms 46212 KB Output is correct