Submission #7494979
Source Code Expand
#define DEB #include<bits/stdc++.h> #include<unistd.h> #define REP(i,m) for(int i=0;i<(m);++i) #define REPN(i,m,in) for(int i=(in);i<(m);++i) #define ALL(t) (t).begin(),(t).end() #define CLR(a) memset((a),0,sizeof(a)) #define pb push_back #define mp make_pair #define fr first #define sc second using namespace std; #ifdef DEB #define dump(x) cerr << #x << " = " << (x) << endl #define prl cerr<<"called:"<< __LINE__<<endl template<class T> void debug(T a,T b){ for(;a!=b;++a) cerr<<*a<<' ';cerr<<endl;} #else #define dump(x) ; #define prl ; template<class T> void debug(T a,T b){ ;} #endif template<class T> void chmin(T& a,const T& b) { if(a>b) a=b; } template<class T> void chmax(T& a,const T& b) { if(a<b) a=b; } typedef long long int lint; typedef pair<int,int> pi; namespace std{ template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.fr<<','<<a.sc<<')'; return out; } } int L=36; const lint INF=1e18; lint H=(1<<18); lint a,b,x; pair<lint,int> baby[1<<18]; lint solve(){ cin>>a>>b>>x; if(a==x) return 0; lint res=0; while(L>0 && !(b>>(L-1)&1)){ if(a==x) return res; if(x>>(L-1)&1) return -1; if(a>>(L-1)&1){ a=(a/2)^((a&1)*b); ++res; } --L; } H = 1 << ((L + 1) / 2); if(a==x) return res; lint conv_H[36]={0}; REP(i,L){ lint cur=(1ll<<i); REP(j,H){ cur=(cur/2)^((cur&1)*b); } conv_H[i]=cur; } lint cur=x; REP(i,H){ cur=(cur/2)^((cur&1)*b); baby[i]=mp(cur,i+1); } sort(baby,baby+H); lint ans=INF; cur=a; REP(i,H){ lint c=0; REP(j,L) if(cur>>j&1) c^=conv_H[j]; int pos=lower_bound(baby,baby+H,mp(c+1,-1))-baby; --pos; if(pos>=0 && baby[pos].fr==c) chmin(ans,H*(i+1)-baby[pos].sc); cur=c; } if(ans==INF) return -1; return ans+res; } int main(){ printf("%lld\n",solve()); return 0; }
Submission Info
Submission Time | |
---|---|
Task | K - 乱数調整 |
User | Inoel |
Language | C++14 (GCC 5.4.1) |
Score | 300 |
Code Size | 2014 Byte |
Status | AC |
Exec Time | 129 ms |
Memory | 4352 KB |
Judge Result
Set Name | Subtask | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 30 / 30 | 270 / 270 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Subtask | subtask_00.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt, subtask_12.txt, subtask_13.txt, subtask_14.txt, subtask_15.txt, subtask_16.txt, subtask_17.txt, subtask_18.txt, subtask_19.txt |
All | scrambled_00.txt, scrambled_01.txt, scrambled_02.txt, scrambled_03.txt, scrambled_04.txt, scrambled_05.txt, scrambled_06.txt, scrambled_07.txt, scrambled_08.txt, scrambled_09.txt, scrambled_10.txt, scrambled_11.txt, scrambled_12.txt, scrambled_13.txt, scrambled_14.txt, scrambled_15.txt, scrambled_16.txt, scrambled_17.txt, scrambled_18.txt, scrambled_19.txt, scrambled_20.txt, scrambled_21.txt, scrambled_22.txt, scrambled_23.txt, scrambled_24.txt, scrambled_25.txt, scrambled_26.txt, scrambled_27.txt, scrambled_28.txt, scrambled_29.txt, scrambled_30.txt, scrambled_31.txt, scrambled_32.txt, scrambled_33.txt, scrambled_34.txt, scrambled_35.txt, scrambled_36.txt, scrambled_37.txt, scrambled_38.txt, scrambled_39.txt, scrambled_40.txt, scrambled_41.txt, scrambled_42.txt, subtask_00.txt, subtask_01.txt, subtask_02.txt, subtask_03.txt, subtask_04.txt, subtask_05.txt, subtask_06.txt, subtask_07.txt, subtask_08.txt, subtask_09.txt, subtask_10.txt, subtask_11.txt, subtask_12.txt, subtask_13.txt, subtask_14.txt, subtask_15.txt, subtask_16.txt, subtask_17.txt, subtask_18.txt, subtask_19.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
scrambled_00.txt | AC | 1 ms | 256 KB |
scrambled_01.txt | AC | 1 ms | 256 KB |
scrambled_02.txt | AC | 1 ms | 256 KB |
scrambled_03.txt | AC | 1 ms | 256 KB |
scrambled_04.txt | AC | 1 ms | 256 KB |
scrambled_05.txt | AC | 1 ms | 256 KB |
scrambled_06.txt | AC | 1 ms | 256 KB |
scrambled_07.txt | AC | 1 ms | 256 KB |
scrambled_08.txt | AC | 1 ms | 256 KB |
scrambled_09.txt | AC | 1 ms | 256 KB |
scrambled_10.txt | AC | 1 ms | 256 KB |
scrambled_11.txt | AC | 1 ms | 256 KB |
scrambled_12.txt | AC | 1 ms | 256 KB |
scrambled_13.txt | AC | 1 ms | 256 KB |
scrambled_14.txt | AC | 1 ms | 256 KB |
scrambled_15.txt | AC | 61 ms | 4352 KB |
scrambled_16.txt | AC | 1 ms | 256 KB |
scrambled_17.txt | AC | 1 ms | 256 KB |
scrambled_18.txt | AC | 61 ms | 4352 KB |
scrambled_19.txt | AC | 61 ms | 4352 KB |
scrambled_20.txt | AC | 129 ms | 4352 KB |
scrambled_21.txt | AC | 126 ms | 4352 KB |
scrambled_22.txt | AC | 128 ms | 4352 KB |
scrambled_23.txt | AC | 127 ms | 4352 KB |
scrambled_24.txt | AC | 129 ms | 4352 KB |
scrambled_25.txt | AC | 61 ms | 4352 KB |
scrambled_26.txt | AC | 128 ms | 4352 KB |
scrambled_27.txt | AC | 126 ms | 4352 KB |
scrambled_28.txt | AC | 1 ms | 256 KB |
scrambled_29.txt | AC | 1 ms | 256 KB |
scrambled_30.txt | AC | 1 ms | 256 KB |
scrambled_31.txt | AC | 1 ms | 256 KB |
scrambled_32.txt | AC | 1 ms | 256 KB |
scrambled_33.txt | AC | 1 ms | 256 KB |
scrambled_34.txt | AC | 1 ms | 256 KB |
scrambled_35.txt | AC | 1 ms | 256 KB |
scrambled_36.txt | AC | 1 ms | 256 KB |
scrambled_37.txt | AC | 1 ms | 256 KB |
scrambled_38.txt | AC | 1 ms | 256 KB |
scrambled_39.txt | AC | 128 ms | 4352 KB |
scrambled_40.txt | AC | 128 ms | 4352 KB |
scrambled_41.txt | AC | 128 ms | 4352 KB |
scrambled_42.txt | AC | 129 ms | 4352 KB |
subtask_00.txt | AC | 1 ms | 256 KB |
subtask_01.txt | AC | 1 ms | 256 KB |
subtask_02.txt | AC | 1 ms | 256 KB |
subtask_03.txt | AC | 1 ms | 256 KB |
subtask_04.txt | AC | 1 ms | 256 KB |
subtask_05.txt | AC | 1 ms | 256 KB |
subtask_06.txt | AC | 1 ms | 256 KB |
subtask_07.txt | AC | 1 ms | 256 KB |
subtask_08.txt | AC | 1 ms | 256 KB |
subtask_09.txt | AC | 1 ms | 256 KB |
subtask_10.txt | AC | 1 ms | 256 KB |
subtask_11.txt | AC | 1 ms | 256 KB |
subtask_12.txt | AC | 1 ms | 256 KB |
subtask_13.txt | AC | 1 ms | 256 KB |
subtask_14.txt | AC | 1 ms | 256 KB |
subtask_15.txt | AC | 1 ms | 256 KB |
subtask_16.txt | AC | 1 ms | 256 KB |
subtask_17.txt | AC | 1 ms | 256 KB |
subtask_18.txt | AC | 1 ms | 256 KB |
subtask_19.txt | AC | 1 ms | 256 KB |