QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#594979#7937. Fast XORtingMath4Life2020Compile Error//C++203.1kb2024-09-28 11:47:442024-09-28 11:47:58

Judging History

你现在查看的是最新测评结果

  • [2024-09-28 11:47:58]
  • 评测
查看
  • [2024-09-28 11:47:44]
  • 提交

answer

#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
using ll = int; using pii = pair<ll,ll>;


ll e2(ll x) {
	return (1LL<<x);
}

struct hashPii {
	ll operator()(const pii &p) const { return p.first + ((p.second+1)<<18); }
};

template <class K, class V>
using ht =
    gp_hash_table<K, V, hashPii, equal_to<K>, direct_mask_range_hashing<>,
                  linear_probe_fn<>,
                  hash_standard_resize_policy<hash_exponential_size_policy<>,
                                              hash_load_check_resize_trigger<>, true>>;

struct ntrie {
	//gp_hash_table<pair<ll,ll>,ll,hashPii> cnt;
	ht<pii,ll> cnt;
	vector<ll> nf,nr;
	vector<pii> vlist;
	ll E;
	ntrie(ll Ec) {
		E=Ec;
	}
	ntrie(ll x0, ll Ec) {
		cnt.resize(Ec+1);
		E=Ec;
		cnt[{0,-1}]=1;
		vlist.push_back({0,-1});
		for (ll j=0;j<E;j++) {
			ll xn = (x0>>(E-1-j))<<(E-1-j);
			cnt[{xn,j}]=1;
			vlist.push_back({xn,j});
			nf.push_back(0);
			nr.push_back(0);
		}
	}
	ll extract() {
		ll ans = 0;
		for (ll j=0;j<E;j++) {
			ans += min(nf[j],nr[j]);
		}
		return ans;
	}
	ll extractR() {
		ll ans = 0;
		for (ll j=0;j<E;j++) {
			ans += nr[j];
		}
		return ans;
	}
};

ntrie merge(ntrie t1, ntrie t2, ll E) {
	ntrie t0 = ntrie(E);
	for (ll i=0;i<E;i++) {
		t0.nr.push_back(t1.nr[i]+t2.nr[i]);
		t0.nf.push_back(t1.nf[i]+t2.nf[i]);
	}
	ll L1 = t1.vlist.size();
	ll L2 = t2.vlist.size();
	ll i1 = 0; ll i2 = 0;
	while (i1<L1 && i2<L2) {
		pii a = t1.vlist[i1]; pii b = t2.vlist[i2];
		if (a.first>b.first) {
			t0.vlist.push_back(b); i2++;
		} else if (a.first<b.first) {
			t0.vlist.push_back(a); i1++;
		} else {
			if (a.second>b.second) {
				t0.vlist.push_back(b); i2++;
			} else if (a.second<b.second) {
				t0.vlist.push_back(a); i1++;
			} else {
				t0.vlist.push_back(a); i1++; i2++;
			}
		}
	}
	while (i1<L1) {
		t0.vlist.push_back(t1.vlist[i1++]);
	}
	while (i2<L2) {
		t0.vlist.push_back(t2.vlist[i2++]);
	} 
	t0.cnt.resize(t0.vlist.size());
	for (pii p0: t0.vlist) {
		t0.cnt[p0]=0;
		if (t1.cnt.find(p0)!=t1.cnt.end()) {
			t0.cnt[p0]+=t1.cnt[p0];
		}
		if (t2.cnt.find(p0)!=t2.cnt.end()) {
			t0.cnt[p0]+=t2.cnt[p0];
		}
		ll x = p0.first; ll j = 1+p0.second;
		if (j>=E) {
			continue;
		}
		ll xl = x; ll xh = x+e2(E-1-j);
		t0.nf[j] += t1.cnt[{xl,j}]*t2.cnt[{xh,j}];
		t0.nr[j] += t1.cnt[{xh,j}]*t2.cnt[{xl,j}];
	}
	return t0;
}

ntrie build(vector<ll> a, ll E) {
	ll N = a.size();
	if (N==1) {
		return ntrie(a[0],E);
	}
	vector<ll> b,c;
	for (ll i=0;i<(N/2);i++) {
		b.push_back(a[i]);
	}
	for (ll i=(N/2);i<N;i++) {
		c.push_back(a[i]);
	}
	return merge(build(b,E),build(c,E),E);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	ll N; cin >> N;
	ll E = __builtin_ctz(N);
	vector<ll> a;
	for (ll i=0;i<N;i++) {
		ll x; cin >> x;
		a.push_back(x);
	}
	ntrie troot = build(a,E);
	ll ans = troot.extractR();
	ans = min(ans,1+troot.extract());
	cout << ans << "\n";
}
Source code, Language: C++20

Details 

In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/gthr.h:148,
                 from /usr/include/c++/13/ext/atomicity.h:35,
                 from /usr/include/c++/13/bits/ios_base.h:39,
                 from /usr/include/c++/13/streambuf:43,
                 from /usr/include/c++/13/bits/streambuf_iterator.h:35,
                 from /usr/include/c++/13/iterator:66,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:54,
                 from answer.code:3:
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:102:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  102 | __gthrw(pthread_once)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:102:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:103:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  103 | __gthrw(pthread_getspecific)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:103:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:104:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  104 | __gthrw(pthread_setspecific)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:104:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:106:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  106 | __gthrw(pthread_create)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:106:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:107:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  107 | __gthrw(pthread_join)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:107:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:108:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  108 | __gthrw(pthread_equal)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:108:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:109:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  109 | __gthrw(pthread_self)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:109:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:110:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  110 | __gthrw(pthread_detach)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:110:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:112:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  112 | __gthrw(pthread_cancel)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:112:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:114:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  114 | __gthrw(sched_yield)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:114:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:116:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  116 | __gthrw(pthread_mutex_lock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:116:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:117:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  117 | __gthrw(pthread_mutex_trylock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:117:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:119:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
  119 | __gthrw(pthread_mutex_timedlock)
      | ^~~~~~~
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:119:1: error: attribute value ‘tune=native’ was already specified in ‘target’ attribute
/usr/include/x86_64-linux-gnu/c++/13/bits/gthr-default.h:121:1: error: attribute value ‘t...
English 繁體中文 简体中文

Server Time: 2024-12-05 00:33:22 | OpenSource Project