QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#121422 | #6319. Parallel Processing (Easy) | xaphoenix | WA | 1ms | 3448kb | C++17 | 4.2kb | 2023-07-08 04:59:15 | 2023-07-08 04:59:17 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LC k << 1
#define RC k << 1 | 1
#define IO cin.sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define rep(i,a,n) for (int i = a; i < n; i++)
#define repn(i,a,n) for (int i = a; i <= n; i++)
#define per(i,a,n) for (int i = n - 1; i >= a; i--)
#define pern(i,a,n) for (int i = n; i >= a; i--)
typedef long long LL;
typedef unsigned long long ull;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef pair<int, LL> pii;
template<typename T> void down(T &x, T y) { if (x > y) x = y; }
const int N = 110000;
const int M = 610000;
const int mod = 998244353;
const int inf = (int)1e9;
const LL INF = (LL)1e12 + 5;
const double eps = 1e-9;
const double pi = acos(-1.0);
int n, mx, a[20];
bool yes = false;
vector<PII> res;
vector<PII> ans;
void dfs(int dep) {
if (yes) return;
int sum = 0;
repn(i, 1, n) if (a[i] > 1) sum ++;
if (sum <= 0) {
yes = true;
for (auto pr : res) ans.pb(pr);
return;
}
if (dep == 0 && sum > 0) return;
if (dep == 1 && sum > 4) return;
if (dep == 2 && sum > 8) return;
if (dep == 3 && sum > 12) return;
vector<PII> tmp; tmp.clear();
repn(i, 1, n) {
if (a[i] == 1) continue;
tmp.pb(mp(a[a[i] - 1] - a[i], i));
}
sort(all(tmp));
int tot = tmp.size();
if (tot < 4) {
rep(i, 0, tot) {
int id = tmp[i].se;
res.pb(mp(id, a[id] - 1));
a[id] += tmp[i].fi;
}
dfs(dep - 1);
rep(i, 0, tot) {
res.pop_back();
a[tmp[i].se] -= tmp[i].fi;
}
}
else {
rep(i, 0, tot) {
res.pb(mp(tmp[i].se, a[tmp[i].se] - 1));
a[tmp[i].se] += tmp[i].fi;
rep(j, i + 1, tot) {
res.pb(mp(tmp[j].se, a[tmp[j].se] - 1));
a[tmp[j].se] += tmp[j].fi;
rep(k, j + 1, tot) {
res.pb(mp(tmp[k].se, a[tmp[k].se] - 1));
a[tmp[k].se] += tmp[k].fi;
rep(s, k + 1, tot) {
res.pb(mp(tmp[s].se, a[tmp[s].se] - 1));
a[tmp[s].se] += tmp[s].fi;
dfs(dep - 1);
res.pop_back();
a[tmp[s].se] -= tmp[s].fi;
}
res.pop_back();
a[tmp[k].se] -= tmp[k].fi;
}
res.pop_back();
a[tmp[j].se] -= tmp[j].fi;
}
res.pop_back();
a[tmp[i].se] -= tmp[i].fi;
}
}
}
//vector<int> b[20], c[20];
vector<int> d[20];
int main()
{
IO;
d[16] = {2, 1, 4, 3, 6, 5, 8, 7, 3, 2, 4, 2,8, 6,10, 9,5, 4,6,
4,8, 4,11, 10,9, 8,11, 8,13, 12,15, 14,12, 11,13, 11,10, 8,16, 15,14, 13,15, 13,16, 13,7, 6};
d[15] = {2, 1,3, 2,4, 3,5, 4,4, 2,6, 5,3, 1,8, 7,5, 3,6, 3,9, 8,11, 10,7,
6,9, 6,12, 11,14, 13,10, 9,11, 9,12, 9,15, 14,13, 12,14, 12,15, 12,8, 6};
d[14] = {2, 1,3,2,4, 3,5, 4,4,2,5, 3,6, 5,3, 1,6, 3,7, 6,8, 7,10, 9,8, 6,7, 3,11,
10,13, 12,9, 8,10, 8,11, 8,14, 13,12, 11,13, 11,14, 11,5, 1 };
cin >> n;
repn(i, 1, n) {
a[i] = i; //b[i].pb(i);
}
if (n < 14) {
repn(i, 1, 5) {
dfs(i);
if (yes) break;
}
int tot = ans.size(), cnt = (tot + 3) / 4;
cout << cnt << "\n";
for (auto pr : ans) {
cout << pr.fi << " " << pr.se << " " << pr.fi << "\n";
}
repn(i, 1, cnt * 4 - tot) {
cout << "2000 2000 2000\n";
}
}
else {
int tot = (int)d[n].size() / 2, cnt = (tot + 3) / 4;
cout << cnt << "\n";
rep(i, 0, tot) {
cout << d[n][2 * i] << " " << d[n][2 * i + 1] << " " << d[n][2 * i] << "\n";
}
repn(i, 1, cnt * 4 - tot) {
cout << "2000 2000 2000\n";
}
}
/*
int tot = ans.size();
rep(i, 0, tot) {
rep(j, i, min(i + 4, tot)) {
int n1 = ans[j].se, n2 = ans[j].fi;
c[n2].clear();
for (auto x : b[n1]) c[n2].pb(x);
for (auto x : b[n2]) c[n2].pb(x);
}
rep(j, i, i + 4) {
int n2 = ans[j].fi;
b[n2].clear();
for (auto x : c[n2]) b[n2].pb(x);
}
i = i + 3;
}
bool can = true;
repn(i, 1, n) {
int n1 = 1;
if (b[i].size() != i) can = false;
for (auto x : b[i]) {
if (x != n1) can = false;
n1 ++;
cout << x << " ";
}
cout << "\n";
}
if (can) cout << "YES\n";
else cout << "NO\n";
*/
for (auto pr : ans) {
cout << pr.fi << " " << pr.se << "\n";
}
return 0;
}
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3448kb
input:
2
output:
1 2 1 2 2000 2000 2000 2000 2000 2000 2000 2000 2000 2 1
result:
wrong output format Extra information in the output file