QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#121423#6319. Parallel Processing (Easy)xaphoenixWA 1ms3492kbC++174.1kb2023-07-08 04:59:532023-07-08 04:59:56

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-08 04:59:56]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3492kb
  • [2023-07-08 04:59:53]
  • 提交

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";
	*/
	return 0;
	
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3492kb

input:

2

output:

1
2 1 2
2000 2000 2000
2000 2000 2000
2000 2000 2000

result:

ok AC

Test #2:

score: -100
Wrong Answer
time: 1ms
memory: 3472kb

input:

4

output:

2
2 1 2
3 2 3
4 3 4
4 2 4
3 1 3
2000 2000 2000
2000 2000 2000
2000 2000 2000

result:

wrong answer A[4] is not (1, …, 4)