제출 #818014

#제출 시각아이디문제언어결과실행 시간메모리
818014farhan132XOR Sum (info1cup17_xorsum)C++17
100 / 100
1033 ms37680 KiB
/***Farhan132***/ #pragma GCC optimize("Ofast,fast-math") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") #pragma GCC optimization ("unroll-loops") #include <bits/stdc++.h> using namespace std; typedef int ll; typedef double dd; typedef pair<ll , ll> ii; typedef tuple < ll, ll, ll > tp; #define ff first #define ss second #define pb push_back #define in insert #define bug printf("**!\n") #define mem(a , b) memset(a, b ,sizeof(a)) #define front_zero(n) __builtin_clz(n) #define back_zero(n) __builtin_ctzll(n) #define total_one(n) __builtin_popcount(n) #define clean fflush(stdout) const ll mod = (ll) 998244353; // const ll mod = (ll) 1e9 + 7; const ll inf = numeric_limits<int>::max()-5; const ll INF = (ll)2e18; ll dx[]={0,1,0,-1}; ll dy[]={1,0,-1,0}; ll dxx[]={0,1,0,-1,1,1,-1,-1}; ll dyy[]={1,0,-1,0,1,-1,1,-1}; mt19937 rng(chrono::system_clock::now().time_since_epoch().count()); #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; const ll N = 1e6 + 5; ll a[N]; void solve(){ ll n; cin >> n; ll ans = 0; vector < ii > A; for(ll i = 1; i <= n; i++) cin >> a[i], A.pb({0, i}); for(ll b = 0; b < 30; b++){ vector < ii > B; ll now_bit = (1 << b); ll nxt_bit = (1 << (b + 1)); for(auto [x, i] : A){ if((a[i] >> b) & 1) continue; B.pb({x, i}); } for(auto [x, i] : A){ if((a[i] >> b) & 1){ B.pb({x + now_bit, i}); } } A = B; long long cnt = 0; ll l = n, r = n; for(ll i = 0; i < n; i++){ while(l > 0 && A[l - 1].ff >= now_bit - A[i].ff) l--; while(r > 0 && A[r - 1].ff >= nxt_bit - A[i].ff) r--; if(r > i){ cnt += r - max(i, l); } } l = n; for(ll i = 0; i < n; i++){ while(l > 0 && A[l - 1].ff >= now_bit + nxt_bit - A[i].ff) l--; cnt += n - max(l, i); } if(cnt & 1) ans |= (1 << b); } cout << ans << '\n'; return; } int main() { #ifdef LOCAL freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); auto start_time = clock(); #else // freopen("subsequence.in", "r", stdin); // freopen("subsequence.out", "w", stdout); ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); #endif //precalc(); ll T = 1, CT = 0; //cin >> T; while(T--){ // cout << "Case #" << ++CT << ": "; solve(); } #ifdef LOCAL auto end_time = clock(); cerr<< "Execution time: "<<(end_time - start_time)*(int)1e3/CLOCKS_PER_SEC<<" ms\n"; #endif return 0; }

컴파일 시 표준 에러 (stderr) 메시지

xorsum.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("unroll-loops")
      | 
xorsum.cpp: In function 'int main()':
xorsum.cpp:113:15: warning: unused variable 'CT' [-Wunused-variable]
  113 |     ll T = 1, CT = 0; //cin >> T;
      |               ^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...