QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#61577 | #1807. Distribute the Bars | Alinxester | WA | 16ms | 29100kb | C++14 | 2.5kb | 2022-11-14 10:07:23 | 2022-11-14 10:07:24 |
Judging History
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