QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#97697#6320. Parallel Processing (Hard)whatever#WA 3ms4068kbC++146.0kb2023-04-17 22:44:292023-04-17 22:44:31

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-17 22:44:31]
  • 评测
  • 测评结果：WA
  • 用时：3ms
  • 内存：4068kb
查看
  • [2023-04-17 22:44:29]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
vector<vector<vector<int> > > ans;
void op(vector<vector<int> > v)
{
/*	bitset<2005> A,B,C,D;
	A=(s[v[0][1]]^s[v[0][2]]);
	B=(s[v[1][1]]^s[v[1][2]]);
	C=(s[v[2][1]]^s[v[2][2]]);
	D=(s[v[3][1]]^s[v[3][2]]);
	s[v[0][0]]=A;
	s[v[1][0]]=B;
	s[v[2][0]]=C;
	s[v[3][0]]=D;*/
	ans.push_back(v);
}
int N;

vector<vector<vector<int> > > solve2(int n)
{
	if(n>=33&&n!=38||n==23)
	{
		auto qaq=solve2(n-15);
		vector<vector<vector<int> > > qwq=qaq;
		for(int i=0;i<qwq.size();i++)
		{
			for(int j=0;j<qwq[i].size();j++)
			{
				for(int k=0;k<qwq[i][j].size();k++)
					qwq[i][j][k]+=15;
			}
		}
		qwq.insert(qwq.begin(),{{2,1,2},{4,3,4},{6,5,6},{8,7,8}});
		qwq.insert(qwq.begin(),{{4,2,4},{8,6,8},{12,11,12},{10,9,10}});
		qwq.insert(qwq.begin(),{{6,4,6},{8,4,8},{14,13,14},{16,15,16}});
		qwq.insert(qwq.begin(),{{3,2,3},{5,4,5},{10,8,10},{14,12,14}});
		qwq.insert(qwq.begin(),{{7,6,7},{9,8,9},{12,10,12},{14,10,14}});
		qwq.insert(qwq.begin(),{{11,10,11},{13,12,13},{15,14,15},{16,14,16}});
		return qwq;
	}
	ans.clear();
//	bitset<2005> s[2005];
	int fa[2005]={},cnt[2005]={};
	for(int i=1;i<=n;i++) fa[i]=i-1,cnt[i-1]=1;
	for(int i=1;i<=n;i++)
	{
		if(n%10==6&&i<=6)
		{
			
			vector<vector<int> > v;
			bitset<2005> qwq;
			qwq.reset();
			int C=4;
			for(int j=1;j<=n;j++)
			{
				if(fa[j]!=0&&cnt[j]&&!qwq[fa[j]]&&fa[fa[j]]==0)
				{
					v.push_back({j,fa[j],j});
					--cnt[fa[j]],++cnt[fa[fa[j]]],fa[j]=fa[fa[j]],qwq[j]=1;
					--C;
				}
				if(!C) break;
			}
			for(int j=1;j<=n;j++)
			{
				if(fa[j]!=0&&cnt[j]&&!qwq[fa[j]])
				{
					v.push_back({j,fa[j],j});
					--cnt[fa[j]],++cnt[fa[fa[j]]],fa[j]=fa[fa[j]],qwq[j]=1;
					--C;
				}
				if(!C) break;
			}
			for(int j=1;j<=n;j++)
			{
				if(fa[j]!=0&&!qwq[fa[j]]&&fa[fa[j]]==0)
				{
					v.push_back({j,fa[j],j});
					--cnt[fa[j]],++cnt[fa[fa[j]]],fa[j]=fa[fa[j]],qwq[j]=1;
					--C;
				}
				if(!C) break;
			}
			for(int j=1;j<=n;j++)
			{
				if(fa[j]!=0&&!qwq[fa[j]])
				{
					v.push_back({j,fa[j],j});
					--cnt[fa[j]],++cnt[fa[fa[j]]],fa[j]=fa[fa[j]],qwq[j]=1;
					--C;
				}
				if(!C) break;
			}
			if(v.size()==0) break;
			while(v.size()<4) v.insert(v.begin(),{v.back()[0],2000,2000});
			op(v);
			continue;
		}
		vector<vector<int> > v;
		bitset<2005> qwq;
		qwq.reset();
		int C=4;
		for(int j=1;j<=n;j++)
		{
			if(fa[j]!=0&&cnt[j]&&!qwq[fa[j]]&&fa[fa[j]]==0)
			{
				v.push_back({j,fa[j],j});
				--cnt[fa[j]],++cnt[fa[fa[j]]],fa[j]=fa[fa[j]],qwq[j]=1;
				--C;
			}
			if(!C) break;
		}
		for(int j=1;j<=n;j++)
		{
			if(fa[j]!=0&&!qwq[fa[j]]&&fa[fa[j]]==0)
			{
				v.push_back({j,fa[j],j});
				--cnt[fa[j]],++cnt[fa[fa[j]]],fa[j]=fa[fa[j]],qwq[j]=1;
				--C;
			}
			if(!C) break;
		}
		for(int j=1;j<=n;j++)
		{
			if(fa[j]!=0&&cnt[j]&&!qwq[fa[j]])
			{
				v.push_back({j,fa[j],j});
				--cnt[fa[j]],++cnt[fa[fa[j]]],fa[j]=fa[fa[j]],qwq[j]=1;
				--C;
			}
			if(!C) break;
		}
		for(int j=1;j<=n;j++)
		{
			if(fa[j]!=0&&!qwq[fa[j]])
			{
				v.push_back({j,fa[j],j});
				--cnt[fa[j]],++cnt[fa[fa[j]]],fa[j]=fa[fa[j]],qwq[j]=1;
				--C;
			}
			if(!C) break;
		}
		if(v.size()==0) break;
		while(v.size()<4) v.insert(v.begin(),{v.back()[0],2000,2000});
		op(v);
	}
	return ans;
}
vector<vector<vector<int> > > solve1(int n)
{
	ans.clear();
//	bitset<2005> s[2005];
	int fa[2005]={},cnt[2005]={};
	for(int i=1;i<=n;i++) fa[i]=i-1,cnt[i-1]=1;
	for(int i=1;i<=n;i++)
	{
		vector<vector<int> > v;
		bitset<2005> qwq;
		qwq.reset();
		int C=4;
		for(int j=1;j<=n;j++)
		{
			if(fa[j]!=0&&cnt[j]&&!qwq[fa[j]]&&fa[fa[j]]==0)
			{
				v.push_back({j,fa[j],j});
				--cnt[fa[j]],++cnt[fa[fa[j]]],fa[j]=fa[fa[j]],qwq[j]=1;
				--C;
			}
			if(!C) break;
		}
		for(int j=1;j<=n;j++)
		{
			if(fa[j]!=0&&cnt[j]&&!qwq[fa[j]])
			{
				v.push_back({j,fa[j],j});
				--cnt[fa[j]],++cnt[fa[fa[j]]],fa[j]=fa[fa[j]],qwq[j]=1;
				--C;
			}
			if(!C) break;
		}
		for(int j=1;j<=n;j++)
		{
			if(fa[j]!=0&&!qwq[fa[j]]&&fa[fa[j]]==0)
			{
				v.push_back({j,fa[j],j});
				--cnt[fa[j]],++cnt[fa[fa[j]]],fa[j]=fa[fa[j]],qwq[j]=1;
				--C;
			}
			if(!C) break;
		}
		for(int j=1;j<=n;j++)
		{
			if(fa[j]!=0&&!qwq[fa[j]])
			{
				v.push_back({j,fa[j],j});
				--cnt[fa[j]],++cnt[fa[fa[j]]],fa[j]=fa[fa[j]],qwq[j]=1;
				--C;
			}
			if(!C) break;
		}
		if(v.size()==0) break;
		while(v.size()<4) v.insert(v.begin(),{v.back()[0],2000,2000});
		op(v);
	}
	return ans;
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
//	for(int i=1;i<=n;i++) s[i][i]=1;
//	for(int i=1;i<=n;i++) fa[i]=i-1,cnt[i-1]=1;
/*	for(int i=1;i<=n;i++)
	{
		vector<vector<int> > v;
		bitset<2005> qwq;
		qwq.reset();
		int C=4;
		for(int j=1;j<=n;j++)
		{
			if(fa[j]!=0&&cnt[j]&&!qwq[fa[j]])
			{
				v.push_back({j,fa[j],j});
				--cnt[fa[j]],++cnt[fa[fa[j]]],fa[j]=fa[fa[j]],qwq[j]=1;
				--C;
			}
			if(!C) break;
		}
		for(int j=1;j<=n;j++)
		{
			if(fa[j]!=0&&fa[fa[j]]==0&&!qwq[fa[j]])
			{
				v.push_back({j,fa[j],j});
				--cnt[fa[j]],++cnt[fa[fa[j]]],fa[j]=fa[fa[j]];
				--C;
			}
			if(!C) break;
		}
		for(int j=1;j<=n;j++)
		{
			if(fa[j]!=0&&!qwq[fa[j]])
			{
				v.push_back({j,fa[j],j});
				--cnt[fa[j]],++cnt[fa[fa[j]]],fa[j]=fa[fa[j]],qwq[j]=1;
				--C;
			}
			if(!C) break;
		}
		if(v.size()==0) break;
		while(v.size()<4) v.push_back({2,1,2});
		op(v);
	}*/
	vector<vector<vector<int> > > qwq;
	for(int i=0;i<=10000;i++) qwq.push_back({{}});
	for(int i=n;i<=n+4;i++)
	{
		vector<vector<vector<int> > > xx=solve2(i);
		if(xx.size()<qwq.size()) qwq=xx;
		xx=solve1(i);
		if(xx.size()<qwq.size()) qwq=xx;
	}
	ans=qwq;
//	assert(((n-1)*2+4)/5==ans.size());
	cout << ans.size() << "\n";
	for(auto t:ans)
	{
		for(auto y:t)
		{
			for(auto x:y) cout << min(2000ll,x) << " ";
			cout << "\n";
		}
	}
/*	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cout << s[i][j];
		}
		cout << "\n";
	}*/
	return 0;
}
源文件, 语言: C++14

详细

Test #1:

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

input:

17

output:

7
2 1 2 
4 3 4 
6 5 6 
8 7 8 
4 2 4 
3 2 3 
8 6 8 
10 9 10 
6 4 6 
8 4 8 
5 4 5 
11 10 11 
11 8 11 
7 6 7 
9 8 9 
10 8 10 
16 2000 2000 
12 11 12 
14 13 14 
16 15 16 
17 2000 2000 
14 12 14 
13 12 13 
17 16 17 
17 2000 2000 
15 14 15 
16 14 16 
17 14 17

result:

ok AC

Test #2:

score: 0
Accepted
time: 3ms
memory: 3768kb

input:

18

output:

7
2 1 2 
4 3 4 
6 5 6 
8 7 8 
4 2 4 
3 2 3 
8 6 8 
10 9 10 
6 4 6 
8 4 8 
5 4 5 
11 10 11 
11 8 11 
7 6 7 
9 8 9 
10 8 10 
12 11 12 
14 13 14 
16 15 16 
18 17 18 
14 12 14 
13 12 13 
17 16 17 
18 16 18 
15 14 15 
16 14 16 
17 14 17 
18 14 18

result:

ok AC

Test #3:

score: 0
Accepted
time: 3ms
memory: 3796kb

input:

19

output:

8
2 1 2 
4 3 4 
6 5 6 
8 7 8 
4 2 4 
3 2 3 
8 6 8 
10 9 10 
6 4 6 
8 4 8 
5 4 5 
11 10 11 
11 8 11 
7 6 7 
9 8 9 
10 8 10 
12 11 12 
14 13 14 
16 15 16 
18 17 18 
14 12 14 
13 12 13 
18 16 18 
17 16 17 
18 14 18 
15 14 15 
16 14 16 
17 14 17 
19 2000 2000 
19 2000 2000 
19 2000 2000 
19 18 19

result:

ok AC

Test #4:

score: 0
Accepted
time: 3ms
memory: 3752kb

input:

20

output:

8
2 1 2 
4 3 4 
6 5 6 
8 7 8 
4 2 4 
8 6 8 
10 9 10 
12 11 12 
6 4 6 
8 4 8 
12 10 12 
14 13 14 
10 8 10 
12 8 12 
15 14 15 
17 16 17 
15 12 15 
18 17 18 
3 2 3 
5 4 5 
18 15 18 
7 6 7 
9 8 9 
11 10 11 
19 18 19 
13 12 13 
14 12 14 
16 15 16 
20 2000 2000 
20 2000 2000 
17 15 17 
20 19 20

result:

ok AC

Test #5:

score: 0
Accepted
time: 2ms
memory: 3780kb

input:

21

output:

8
2 1 2 
4 3 4 
6 5 6 
8 7 8 
4 2 4 
3 2 3 
8 6 8 
10 9 10 
6 4 6 
8 4 8 
5 4 5 
11 10 11 
11 8 11 
7 6 7 
9 8 9 
10 8 10 
12 11 12 
14 13 14 
16 15 16 
18 17 18 
14 12 14 
13 12 13 
18 16 18 
20 19 20 
16 14 16 
18 14 18 
15 14 15 
21 20 21 
17 16 17 
19 18 19 
20 18 20 
21 18 21

result:

ok AC

Test #6:

score: -100
Wrong Answer
time: 3ms
memory: 4068kb

input:

120

output:

48
11 10 11 
13 12 13 
15 14 15 
16 14 16 
7 6 7 
9 8 9 
12 10 12 
14 10 14 
3 2 3 
5 4 5 
10 8 10 
14 12 14 
6 4 6 
8 4 8 
14 13 14 
16 15 16 
4 2 4 
8 6 8 
12 11 12 
10 9 10 
2 1 2 
4 3 4 
6 5 6 
8 7 8 
26 25 26 
28 27 28 
30 29 30 
31 29 31 
22 21 22 
24 23 24 
27 25 27 
29 25 29 
18 17 18 
20 19...

result:

wrong answer A[3] is not (1, …, 3)
English 繁體中文 简体中文

服务器时间: 2024-12-05 06:42:07 | 开源项目