QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#341971#313. Equation Mod 2ucup-team1209#Compile Error//C++203.8kb2024-02-29 23:41:072024-02-29 23:41:08

Judging History

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

  • [2024-02-29 23:41:08]
  • 评测
查看
  • [2024-02-29 23:41:07]
  • 提交

answer

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native,avx2")

#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l), i##end = (r);i <= i##end;++i)
using std::cin;
using std::cout;

const int N = 5056;

using u64 = unsigned long long;
using u32 = unsigned;

int start;
struct vector {
	static const int M = N / 64;
	u64 a[M + 1];
	bool test(int x) {
		return a[x >> 6] >> (x & 63) & 1;
	}
	u32 substr(int x) {
		return *(u64*)((u32*) a + (x >> 5)) >> (x & 31);
	}
	void set(int x) {
		a[x >> 6] |= 1ull << x;
	}
	void solve_xor(const vector & x, int lim = M - 1) {
		for(int i = start;i < M;++i) {
			a[i] ^= x.a[i];
		}
	}
	int get(const vector & x) {
		u64 ans = 0;
		for(int i = 0;i < M;++i) {
			ans ^= a[i] & x.a[i];
		}
		return std::popcount(ans) % 2;
	}
};
int n, m;
vector a[N], ans;
u32 reverse_bits(u32 x) {
	x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
	x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
	x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
	x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
	return ((x >> 16) | (x << 16));
}
using pr = std::pair<u32, int>;
pr v[N];
int idx[N];

int main() {
	std::ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> m;
	for(int x = 0;x < m;++x) {
		char c;
		for(int i = 0;i <= n;++i) {
			cin >> c;
			if(c & 1) a[x].set(i);
		}
	}
	int r = 0;
	for(int i = 0;i < n;++i) {
		int c = 0;
		for(int j = r;j < m;++j) {
			if(a[j].test(i)) {
				v[c++] = pr(reverse_bits(a[j].substr(i)), j);
			}
		}
		if(c != 0) {
//			sort(v, v + c);
			for(int j = 0;j + 1 < c;++j) {
				a[v[j].second].solve_xor(a[v[j + 1].second]);
			}
			std::swap(a[v[c - 1].second], a[r]);
			idx[r] = i;
			r += 1;
		}
	}
	ans.set(n);
	for(int i = r - 1;i >= 0;--i) {
		if(ans.get(a[i])) {
			ans.set(idx[i]);
		}
	}
	for(int i = 0;i < n;++i) {
		cout << ans.test(i) << ' ';
	}
}




#include<bits/stdc++.h>
#define rep(i, l, r) for(int i = (l), i##end = (r);i <= i##end;++i)
using std::cin;
using std::cout;

const int N = 5056;

using u64 = unsigned long long;
using u32 = unsigned;

int start;
struct vector {
	static const int M = N / 64;
	u64 a[M + 1];
	bool test(int x) {
		return a[x >> 6] >> (x & 63) & 1;
	}
	u32 substr(int x) {
		return *(u64*)((u32*) a + (x >> 5)) >> (x & 31);
	}
	void set(int x) {
		a[x >> 6] |= 1ull << x;
	}
	void solve_xor(const vector & x, int lim = M - 1) {
		for(int i = start;i < M;++i) {
			a[i] ^= x.a[i];
		}
	}
	int get(const vector & x) {
		u64 ans = 0;
		for(int i = 0;i < M;++i) {
			ans ^= a[i] & x.a[i];
		}
		return std::popcount(ans) % 2;
	}
};
int n, m;
vector a[N], ans;
u32 reverse_bits(u32 x) {
	x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
	x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
	x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
	x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
	return ((x >> 16) | (x << 16));
}
using pr = std::pair<u32, int>;
pr v[N];
int idx[N];

int main() {
	std::ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> m;
	for(int x = 0;x < m;++x) {
		char c;
		for(int i = 0;i <= n;++i) {
			cin >> c;
			if(c & 1) a[x].set(i);
		}
	}
	int r = 0;
	for(int i = 0;i < n;++i) {
		int c = 0;
		for(int j = r;j < m;++j) {
			if(a[j].test(i)) {
				v[c++] = pr(reverse_bits(a[j].substr(i)), j);
			}
		}
		if(c != 0) {
			sort(v, v + c);
			for(int j = 0;j + 1 < c;++j) {
				a[v[j].second].solve_xor(a[v[j + 1].second]);
			}
			std::swap(a[v[c - 1].second], a[r]);
			idx[r] = i;
			r += 1;
		}
	}
	ans.set(n);
	for(int i = r - 1;i >= 0;--i) {
		if(ans.get(a[i])) {
			ans.set(idx[i]);
		}
	}
	for(int i = 0;i < n;++i) {
		cout << ans.test(i) << ' ';
	}
}
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:5:
/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-11-29 16:31:50 | OpenSource Project