QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#61577#1807. Distribute the BarsAlinxesterWA 16ms29100kbC++142.5kb2022-11-14 10:07:232022-11-14 10:07:24

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-14 10:07:24]
  • 评测
  • 测评结果:WA
  • 用时:16ms
  • 内存:29100kb
  • [2022-11-14 10:07:23]
  • 提交

answer

#include<bits/stdc++.h>
#define N ((int)1e6 + 2)
#define int long long
#define INF ((int)1e18 + 2)
#define CH 28
#define B 32
#define mod 998244353
#define db double
#define eps 1e-8
#define lowbit(x) (x&-x)
#define rep(i,x,y) for (int i = (x); i <= (y); ++i)
#define drep(i,x,y) for (int i = (x); i >= (y); --i)
#define go(i,u) for (int i = head[u]; i; i = edge[i].next)
#define pii pair<int, int>
#define MP make_pair
#define fir first
#define sec second
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<typename T> inline T rnd(T l,T r) {return uniform_int_distribution<T>(l , r)(rng);}
template<typename T> inline void read (T &t) {
	t = 0; char f = 0, ch = getchar(); long db d = 0.1;
	while (ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
	while (ch <= '9' && ch >= '0') t = t * 10 + ch - 48, ch = getchar();
	if (ch == '.') {
		ch = getchar();
		while (ch <= '9' && ch >= '0') t += d * (ch ^ 48), d *= 0.1, ch = getchar();
	}
	t = (f ? -t : t);
}
template <typename T, typename... Args>
	inline void read (T& t, Args&... args) { read(t); read(args...); }
int prim[N], pric;
bool vis[N];
inline void get_prime () {
	rep (i, 2, N - 1) {
		if (!vis[i]) prim[++pric] = i;
		for (int j = 1; j <= pric && i * prim[j] < N; ++j) {
			vis[i * prim[j]] = true;
			if (!(i % prim[j])) break;
		}
	}
}
int n;
vector<int> vec, ans[N];
int ansc;
inline void divide (int x) {
	rep (j, 1, pric) while (!(x % prim[j]))
		vec.emplace_back(prim[j]), x /= prim[j];
}
signed main() {
	get_prime();
	read(n);
	if (!vis[n]) return printf("-1\n"), 0;
	int sqrt_n = sqrt(n);
	if (sqrt_n * sqrt_n == n) {
		int d = sqrt_n;
		ansc = d;
		rep (i, 1, d) {
			int p = i;
			rep (j, 1, d)
				ans[i].emplace_back((j - 1) * d + p), (++p > d ? p -= d : p);
		}
		rep (i, 1, ansc) {
			printf("%lld ", (int)ans[i].size());
			rep (j, 0, (int)ans[i].size() - 1) printf("%lld ", (ans[i][j] << 1) - 1);
			printf("\n");
		}
		return 0;
	}
	divide(n);
	int d1 = vec[0], d2 = n / vec[0];
	if (d1 > d2) swap(d1, d2);
	ansc = d1;
	rep (i, 1, d1) {
		int p = i;
		rep (j, 1, d1) ans[i].emplace_back((j - 1) * d1 + p), (++p > d1 ? p -= d1 : p);
	}
	int d = (d2 - d1) / 2;
	int l = d1 * d1 + 1, r = n;
	rep (i, 1, d1) {
		rep (j, 1, d) ans[i].emplace_back(l++);
		rep (j, 1, d) ans[i].emplace_back(r--); 
	}
	printf("%lld\n", ansc);
	rep (i, 1, ansc) {
		printf("%lld ", (int)ans[i].size());
		rep (j, 0, (int)ans[i].size() - 1) printf("%lld ", (ans[i][j] << 1) - 1);
		printf("\n");
	}
return 0;
}

详细

Test #1:

score: 0
Wrong Answer
time: 16ms
memory: 29100kb

input:

4

output:

2 1 7 
2 3 5 

result:

wrong answer Not all bars are distributed