QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#100688#6319. Parallel Processing (Easy)SolitaryDream#TL 1351ms121776kbC++201.9kb2023-04-27 17:10:112023-04-27 17:10:11

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-27 17:10:11]
  • 评测
  • 测评结果:TL
  • 用时:1351ms
  • 内存:121776kb
  • [2023-04-27 17:10:11]
  • 提交

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

output:


result: