QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #61579 | #1807. Distribute the Bars | Alinxester | WA | 24ms | 28756kb | C++14 | 2.6kb | 2022-11-14 10:08:36 | 2022-11-14 10:11:23 |
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);
}
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;
}
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;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 17ms
memory: 28616kb
input:
4
output:
2 2 1 7 2 3 5
result:
ok OK (2 groups)
Test #2:
score: 0
Accepted
time: 24ms
memory: 28400kb
input:
2
output:
-1
result:
ok OK (impossible)
Test #3:
score: 0
Accepted
time: 11ms
memory: 28608kb
input:
3
output:
-1
result:
ok OK (impossible)
Test #4:
score: 0
Accepted
time: 17ms
memory: 28756kb
input:
1659
output:
3 553 1 9 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 175 177 179 181 ...
result:
ok OK (3 groups)
Test #5:
score: 0
Accepted
time: 22ms
memory: 28604kb
input:
8941
output:
-1
result:
ok OK (impossible)
Test #6:
score: -100
Wrong Answer
time: 21ms
memory: 28624kb
input:
458
output:
2 228 1 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 101 103 105 107 109 111 113 115 117 119 121 123 125 127 129 131 133 135 137 139 141 143 145 147 149 151 153 155 157 159 161 163 165 167 169 171 173 175 1...
result:
wrong answer Not all bars are distributed