QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #97709 | #6320. Parallel Processing (Hard) | whatever# | WA | 3ms | 4012kb | C++14 | 6.2kb | 2023-04-17 23:08:01 | 2023-04-17 23:08:04 |
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> > > 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;
}
vector<vector<vector<int> > > solve2(int n)
{
if(n!=35&&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}});
// cout << qaq.size() << " " << qwq.size() << "\n";
// if(n==50)exit(0);
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);
}
auto ttt=ans;
auto qwq2=solve1(n);
if(qwq2.size()<ttt.size()) return qwq2;
return ttt;
}
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<=max(n,11ll);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: 2ms
memory: 3864kb
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: 2ms
memory: 3860kb
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: 3888kb
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: 2ms
memory: 3792kb
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: 3ms
memory: 3896kb
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: 4012kb
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)