fork download
copy 
  1. #include <bits/stdc++.h>
  2. namespace bijiEnak {
  3.     using namespace std;
  4.     using ll = long long;
  5.     using ull = unsigned long long;
  6.     #define vi vector<int>
  7.     #define mpii map<int, int>
  8.     #define int long long // on or off
  9.     #define vl vector<ll>
  10.     #define pii pair<int, int>
  11.     #define fr first
  12.     #define sc second
  13.     #define pq priority_queue
  14.     #define mpr make_pair
  15.     #define biji ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);    
  16.     #define fillArr1D(ar, in, n) for(int i = 0; i < n; i++) ar[i] = in
  17.     #define fillArr2D(ar, in, n, m) for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) ar[i][j] = in
  18.     #define fillArr3D(ar, in, n, m, o) for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) for(int k = 0; k < o; k++) ar[i][j][k] = in
  19.     //lower_bound(x) : >= x
  20.     //upper_bound(x) : > x
  21.     const int MOD = 1e9 + 7;
  22.     const int MAXN = 2e5 + 1;
  23.     const string input = {'_', 'i', 'n', 'p', 'u', 't', '.', 't', 'x', 't'};
  24.     const string output = {'_', 'o', 'u', 't', 'p', 'u', 't', '.', 't', 'x', 't'};
  25.     const string input_r = {'r'};
  26.     const string output_w = {'w'};
  27. }
  28. using namespace bijiEnak;
  29.  
  30. bool isQuad(int x) {
  31.     int tmp = sqrt(x);
  32.     return (x == (tmp*tmp));
  33. }
  34.  
  35. void tcsolve() {
  36.     int N; cin >> N;
  37.     vector<int> vc(N); for(auto& i : vc) cin >> i;
  38.     for(int i = 1; i < N; i++) vc[i] = vc[i]^vc[i-1];
  39.  
  40.     vector<int> quad;
  41.     for(int i = 1; i <= N; i++)
  42.         if(isQuad(i)) quad.push_back(i);
  43.  
  44.     set<int> adj[4*N+4];
  45.     for(auto i : quad) {
  46.         for(auto j : vc) {
  47.             adj[j].insert(i^j);
  48.             adj[j].insert(j);
  49.         }
  50.     }
  51.  
  52.     for(auto i : vc) {
  53.         cout << i << " -> ";
  54.         for(auto x : adj[i]) cout << x << " ";
  55.         cout << "\n";
  56.     }
  57.  
  58.     int sum = (isQuad(vc[0]) ? 1 : 0);
  59.     set<int> st; vector<int> freq(4*N+4, 0);
  60.  
  61.     st.insert(vc[0]); freq[vc[0]]++;
  62.     for(int i = 1; i < N; i++) {
  63.         if(isQuad(vc[i])) sum++;
  64.         for(auto x : adj[vc[i]]) {
  65.             auto it = st.lower_bound(x);
  66.             if(it == st.end()) continue;
  67.             sum += freq[x];
  68.         }
  69.         st.insert(vc[i]); freq[vc[i]]++;
  70.     }
  71.  
  72.     int ans = (N*(N+1)) / 2;
  73.     cout << ans-sum << "\n";
  74. }
  75.  
  76. signed main() {
  77.     // freopen(input.c_str(), input_r.c_str(), stdin);
  78.     // freopen(output.c_str(), output_w.c_str(), stdout);
  79.  
  80.     biji int t = 1;
  81.     cin >> t;
  82.     while(t--) tcsolve();
  83.  
  84.     return 0;
  85. }
Success #stdin #stdout 0.01s 5552KB
comments (?)
stdin
copy 
1
8
8 8 5 1 1 4 2 4
stdout
copy 
8 -> 8 9 12 
0 -> 0 1 4 
5 -> 1 4 5 
4 -> 0 4 5 
5 -> 1 4 5 
1 -> 0 1 5 
3 -> 2 3 7 
7 -> 3 6 7 
25
https://ideone.com/3JhCFJ
language:
C++ (gcc 8.3)
created:
1 year 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!