結果
問題 | No.1209 XOR Into You |
ユーザー | WA_TLE |
提出日時 | 2020-08-30 13:42:27 |
言語 | C++17 (gcc 13.2.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 113 ms / 2,000 ms |
コード長 | 2,393 bytes |
コンパイル時間 | 2,383 ms |
コンパイル使用メモリ | 142,752 KB |
実行使用メモリ | 5,696 KB |
最終ジャッジ日時 | 2023-08-09 11:57:52 |
合計ジャッジ時間 | 6,595 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,376 KB |
testcase_02 | AC | 1 ms
4,380 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 37 ms
4,376 KB |
testcase_05 | AC | 38 ms
4,380 KB |
testcase_06 | AC | 82 ms
4,736 KB |
testcase_07 | AC | 87 ms
4,884 KB |
testcase_08 | AC | 79 ms
4,892 KB |
testcase_09 | AC | 80 ms
4,832 KB |
testcase_10 | AC | 66 ms
4,704 KB |
testcase_11 | AC | 79 ms
4,836 KB |
testcase_12 | AC | 73 ms
4,628 KB |
testcase_13 | AC | 82 ms
5,000 KB |
testcase_14 | AC | 69 ms
4,732 KB |
testcase_15 | AC | 73 ms
4,572 KB |
testcase_16 | AC | 75 ms
4,568 KB |
testcase_17 | AC | 70 ms
4,736 KB |
testcase_18 | AC | 99 ms
5,464 KB |
testcase_19 | AC | 72 ms
4,680 KB |
testcase_20 | AC | 82 ms
4,832 KB |
testcase_21 | AC | 62 ms
4,412 KB |
testcase_22 | AC | 86 ms
5,404 KB |
testcase_23 | AC | 86 ms
5,364 KB |
testcase_24 | AC | 88 ms
5,476 KB |
testcase_25 | AC | 101 ms
5,696 KB |
testcase_26 | AC | 102 ms
5,472 KB |
testcase_27 | AC | 101 ms
5,672 KB |
testcase_28 | AC | 101 ms
5,360 KB |
testcase_29 | AC | 101 ms
5,696 KB |
testcase_30 | AC | 101 ms
5,360 KB |
testcase_31 | AC | 106 ms
5,360 KB |
testcase_32 | AC | 108 ms
5,360 KB |
testcase_33 | AC | 107 ms
5,420 KB |
testcase_34 | AC | 113 ms
5,404 KB |
testcase_35 | AC | 104 ms
5,492 KB |
testcase_36 | AC | 106 ms
5,356 KB |
testcase_37 | AC | 92 ms
5,416 KB |
testcase_38 | AC | 83 ms
5,000 KB |
testcase_39 | AC | 75 ms
4,996 KB |
testcase_40 | AC | 87 ms
5,532 KB |
ソースコード
#include<deque> #include<queue> #include<vector> #include<algorithm> #include<iostream> #include<set> #include<cmath> #include<tuple> #include<string> #include<chrono> #include<functional> #include<iterator> #include<random> #include<unordered_set> #include<array> #include<map> #include<iomanip> #include<assert.h> #include<list> #include<bitset> #include<stack> #include<memory> #include<numeric> using namespace std; using namespace std::chrono; typedef long long int llint; typedef long double lldo; #define mp make_pair #define mt make_tuple #define pub push_back #define puf push_front #define pob pop_back #define pof pop_front #define fir first #define sec second #define res resize #define ins insert #define era erase #define REP(i, n) for(int i = 0;i < (n);i++) /*cout<<fixed<<setprecision(20);cin.tie(0);ios::sync_with_stdio(false);*/ const llint mod=1000000007; const llint inf=2.19e15+1; const long double pai=3.141592653589793238462643383279502884197; const long double eps=1e-10; template <class T,class U>bool chmin(T& a,U b){if(a>b){a=b;return true;}return false;} template <class T,class U>bool chmax(T& a,U b){if(a<b){a=b;return true;}return false;} llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);} llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;} template<class T> void SO(T& ve){sort(ve.begin(),ve.end());} template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());} template<class T>llint LBI(const vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();} template<class T>llint UBI(const vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();} int main(void){ int n,i,gen;cin>>n; vector<int>Asa(n-1); vector<int>Bsa(n-1); int sg; cin>>gen;sg=gen; for(i=0;i<n-1;i++){ int now;cin>>now; Asa[i]=now^gen; gen=now; } cin>>gen; if(sg!=gen){cout<<-1<<endl;return 0;} for(i=0;i<n-1;i++){ int now;cin>>now; Bsa[i]=now^gen; gen=now; } vector<pair<int,int>>SB(n-1); for(i=0;i<n-1;i++){SB[i]=mp(Bsa[i],i);} SO(SB); static int seg[262144]={}; llint ans=0; for(i=0;i<n-1;i++){ int p=LBI(SB,mp(Asa[i],0)); if(p>=n||SB[p].fir!=Asa[i]){cout<<-1<<endl;return 0;} int bas=SB[p].sec+131072; SB[p].fir--; SB[p].sec+=n; while(bas>1){ seg[bas]++; if(bas%2==0){ans+=seg[bas+1];} bas/=2; } } cout<<ans<<endl; return 0; } /* a b c a abc c */