QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#100688 | #6319. Parallel Processing (Easy) | SolitaryDream# | TL | 1351ms | 121776kb | C++20 | 1.9kb | 2023-04-27 17:10:11 | 2023-04-27 17:10:11 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,s,t) for(int i=(s),_t=(t); i<=_t; ++i)
#define DOR(i,s,t) for(int i=(s),_t=(t); i>=_t; --i)
typedef long long ll;
const int Mod=7000009;
bool mark[Mod];
int Hash(const vector<int> &v) {
int w=0;
for(auto x: v) w=(w*233+x)%Mod;
return w;
}
struct node {
int a,b;
};
struct state {
vector<int> lp;
vector<vector<node>> ans;
};
void print(vector<vector<node>> ans) {
cout << ans.size() << '\n';
for(auto s: ans) {
FOR(i,0,3) {
int j=min(i,(int)s.size()-1);
cout << s[j].b << ' ' << s[j].a << ' ' << s[j].b << '\n';
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
state q;
q.lp={0};
FOR(i,1,n) q.lp.push_back(i);
vector<vector<int>> f;
FOR(i,2,n) FOR(j,i+1,n) FOR(k,j+1,n) FOR(h,k+1,n) f.push_back({i,j,k,h});
FOR(i,2,n) FOR(j,i+1,n) FOR(k,j+1,n) f.push_back({i,j,k});
FOR(i,2,n) FOR(j,i+1,n) f.push_back({i,j});
FOR(i,2,n) f.push_back({i});
queue<state> Q;
mark[Hash(q.lp)]=1;
Q.push(q);
while(!Q.empty()) {
q=Q.front(),Q.pop();
for(auto v: f) {
state nq=q;
vector<node> op;
int w=1;
for(auto x: v) {
if(q.lp[x]>1) {
nq.lp[x]=q.lp[q.lp[x]-1];
op.push_back({q.lp[x]-1,x});
} else {
w=0;
break;
}
}
if(!w) continue;
w=1;
FOR(i,1,n) if(nq.lp[i]!=1) {w=0;break;}
nq.ans.push_back(op);
if(w) {
print(nq.ans);
return 0;
}
if(mark[Hash(nq.lp)]) continue;
mark[Hash(nq.lp)]=1;
Q.push(nq);
}
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3316kb
input:
2
output:
1 2 1 2 2 1 2 2 1 2 2 1 2
result:
ok AC
Test #2:
score: 0
Accepted
time: 0ms
memory: 5340kb
input:
4
output:
2 2 1 2 3 2 3 4 3 4 4 3 4 3 1 3 4 2 4 4 2 4 4 2 4
result:
ok AC
Test #3:
score: 0
Accepted
time: 2ms
memory: 3368kb
input:
3
output:
2 2 1 2 3 2 3 3 2 3 3 2 3 3 1 3 3 1 3 3 1 3 3 1 3
result:
ok AC
Test #4:
score: 0
Accepted
time: 0ms
memory: 5484kb
input:
5
output:
3 2 1 2 3 2 3 4 3 4 5 4 5 3 1 3 4 2 4 5 3 5 5 3 5 5 1 5 5 1 5 5 1 5 5 1 5
result:
ok AC
Test #5:
score: 0
Accepted
time: 2ms
memory: 5504kb
input:
6
output:
3 2 1 2 3 2 3 4 3 4 5 4 5 3 1 3 4 2 4 5 3 5 6 5 6 5 1 5 6 3 6 6 3 6 6 3 6
result:
ok AC
Test #6:
score: 0
Accepted
time: 4ms
memory: 5856kb
input:
7
output:
3 2 1 2 3 2 3 4 3 4 6 5 6 3 1 3 4 2 4 5 4 5 7 6 7 5 2 5 6 4 6 7 4 7 7 4 7
result:
ok AC
Test #7:
score: 0
Accepted
time: 19ms
memory: 8156kb
input:
8
output:
3 2 1 2 4 3 4 6 5 6 8 7 8 3 2 3 4 2 4 7 6 7 8 6 8 5 4 5 6 4 6 7 4 7 8 4 8
result:
ok AC
Test #8:
score: 0
Accepted
time: 291ms
memory: 34152kb
input:
9
output:
4 2 1 2 3 2 3 4 3 4 5 4 5 3 1 3 4 2 4 6 5 6 8 7 8 5 3 5 6 3 6 7 6 7 9 8 9 7 3 7 8 6 8 9 6 9 9 6 9
result:
ok AC
Test #9:
score: 0
Accepted
time: 1351ms
memory: 121776kb
input:
10
output:
4 2 1 2 3 2 3 4 3 4 6 5 6 3 1 3 4 2 4 7 6 7 9 8 9 5 4 5 6 4 6 7 4 7 10 9 10 8 7 8 9 7 9 10 7 10 10 7 10
result:
ok AC
Test #10:
score: -100
Time Limit Exceeded
input:
11