QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #97697 | #6320. Parallel Processing (Hard) | whatever# | WA | 3ms | 4068kb | C++14 | 6.0kb | 2023-04-17 22:44:29 | 2023-04-17 22:44:31 |
Judging History
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;
}
Details
Tip: Click on the bar to expand more detailed information
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)