fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define pb push_back
  4. #define eb emplace_back
  5. #define pu push
  6. #define ins insert
  7. #define fi first
  8. #define se second
  9. #define all(a) a.begin(),a.end()
  10. #define fastio ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  11.  
  12. using namespace std;
  13. //mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());
  14.  
  15. typedef pair<int, int> pii;
  16. const int mod = 2147483647;
  17. const int inf = 1e9 + 7;
  18.  
  19. signed main(){
  20.     int n; cin >> n;
  21.     int a[n], b[n];
  22.     vector<int> s;
  23.     for(int i = 0; i < n; i++){
  24.         cin >> a[i];
  25.     }
  26.     for(int i = 0; i < n; i++){
  27.         cin >> b[i];
  28.         if(i > 0) s.pb(b[i] ^ b[i - 1]);
  29.     } s.pb(INT_MAX);
  30.     for(int i = 1; i < n * 2 - 1; i++){
  31.         int x = a[i % n] ^ a[(i - 1) % n];
  32.         s.pb(x);
  33.     }
  34.     int kmp[n * 2 + 1];
  35.     kmp[0] = 0;
  36.     vector<pair<int, int> > ans;
  37.     for(int i = 1; i < s.size(); i++){
  38.         int j = kmp[i - 1];
  39.         while(j > 0 && s[j] != s[i]){   //aa#aaaaa
  40.             j = kmp[j - 1];
  41.         }
  42.         if(s[j] == s[i]) ++j;
  43.         kmp[i] = j;
  44.         if(i > n - 1 && kmp[i] == n - 1){
  45.             cout << b[0] << endl;
  46.             int x = a[i - n - n + 2] ^ b[0];
  47.             ans.pb({i - n - n + 2, x});
  48.         }
  49.     } cout << "--";
  50.     sort(ans.begin(), ans.end());
  51.     for(pii i : ans) cout << i.first << " " << i.se << "\n";
  52.     return 0;
  53. }
  54.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin 
5
0 0 0 0 0
2 2 2 2 2
stdout 
2
2
2
2
4
--0 2
1 2
2 2
3 2
4 4
https://ideone.com/5XtqC9
language:
C++14 (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!