QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#524092#4930. LCS of PermutationsModyKachef8 225ms3932kbC++231.6kb2024-08-19 10:17:582024-08-19 10:17:59

Judging History

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

  • [2024-08-19 10:17:59]
  • 评测
  • 测评结果:8
  • 用时:225ms
  • 内存:3932kb
  • [2024-08-19 10:17:58]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define int long long 

vector<int> ans[7][7][7][7][3]; 

int lcs(vector<int> p1 , vector<int> p2){
    int n = p1.size(); 
    vector<int> id(n);
    for (int i = 0 ; i < n ; i++) id[p1[i]] = i; 
    for (int i = 0 ; i < n ; i++) p2[i] = id[p2[i]]; 
    vector<int> dp;
    for (int i = 0 ; i < n ; i++){
        int x = lower_bound(dp.begin() , dp.end() , p2[i]) - dp.begin();
        if (x == dp.size()) dp.push_back(p2[i]);
        else dp[x] = p2[i]; 
    }
    return dp.size(); 
}

void proc(){
    for (int n = 1 ; n <= 6 ; n++){
        vector<int> p[3];
        for (int i = 0 ; i < n ; i++) for (int j = 0 ; j < 3 ; j++) p[j].push_back(i);
        do {
            do {
                int a = lcs(p[0] , p[1]) , b = lcs(p[0] , p[2]) , c = lcs(p[1] , p[2]); 
                for (int j = 0 ; j < 3 ; j++) ans[n][a][b][c][j] = p[j]; 
            } while(next_permutation(p[1].begin() , p[1].end()));
        } while(next_permutation(p[2].begin() , p[2].end())); 
    }
}

void doWork(){
    int n , a , b , c , o;
    cin >> n >> a >> b >> c >> o;
    if (n > 6) {cout << "bruh"; return;}
    if (ans[n][a][b][c][0].empty()) {cout << "NO"; return;}
    cout << "YES\n";
    for (int j = 0 ; j < 3 ; j++){
        for (int i = 0 ; i < n ; i++){
            cout << ans[n][a][b][c][j][i] + 1 << ' '; 
        }
        cout << '\n';
    }
}

signed main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    proc(); 
    int t; cin >> t;
    while(t--){
        doWork(); cout << '\n';
    }
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 0
Wrong Answer
time: 209ms
memory: 3932kb

input:

632
512 1 1 512 1
201 1 1 201 1
155 1 1 155 1
129 1 1 129 1
345 1 1 345 1
454 1 1 454 1
614 1 1 614 1
11 1 1 11 1
492 1 1 492 1
357 1 1 357 1
300 1 1 300 1
295 1 1 295 1
607 1 1 607 1
442 1 1 442 1
14 1 1 14 1
79 1 1 79 1
584 1 1 584 1
431 1 1 431 1
343 1 1 343 1
64 1 1 64 1
548 1 1 548 1
101 1 1 10...

output:

bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
YES
1 2 3 
3 2 1 
3 2 1 

bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh...

result:

wrong answer Token parameter [name=yes/no] equals to "bruh", doesn't correspond to pattern "[yY][eE][sS]|[nN][oO]" (test case 1)

Subtask #2:

score: 8
Accepted

Test #9:

score: 8
Accepted
time: 225ms
memory: 3656kb

input:

40011
1 1 1 1 1
2 1 1 1 1
2 1 1 2 1
2 1 2 2 1
2 2 2 2 1
3 1 1 1 1
3 1 1 2 1
3 1 1 3 1
3 1 2 2 1
3 1 2 3 1
3 1 3 3 1
3 2 2 2 1
3 2 2 3 1
3 2 3 3 1
3 3 3 3 1
4 1 1 1 1
4 1 1 2 1
4 1 1 3 1
4 1 1 4 1
4 1 2 2 1
4 1 2 3 1
4 1 2 4 1
4 1 3 3 1
4 1 3 4 1
4 1 4 4 1
4 2 2 2 1
4 2 2 3 1
4 2 2 4 1
4 2 3 3 1
4 2 ...

output:

YES
1 
1 
1 

NO
YES
1 2 
2 1 
2 1 

NO
YES
1 2 
1 2 
1 2 

NO
NO
YES
1 2 3 
3 2 1 
3 2 1 

YES
1 2 3 
3 2 1 
3 1 2 

NO
NO
YES
1 2 3 
2 3 1 
3 1 2 

YES
1 2 3 
3 1 2 
3 1 2 

NO
YES
1 2 3 
1 2 3 
1 2 3 

NO
NO
NO
YES
1 2 3 4 
4 3 2 1 
4 3 2 1 

YES
1 2 3 4 
4 3 2 1 
3 4 1 2 

YES
1 2 3 4 
4 3 2 1 
...

result:

ok Correct (40011 test cases)

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Wrong Answer

Test #58:

score: 0
Wrong Answer
time: 209ms
memory: 3652kb

input:

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

output:

bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
bruh
...

result:

wrong answer Token parameter [name=yes/no] equals to "bruh", doesn't correspond to pattern "[yY][eE][sS]|[nN][oO]" (test case 1)

Subtask #6:

score: 0
Skipped

Dependency #2:

100%
Accepted

Dependency #3:

0%