QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#245607	#7687. Randias Permutation Task	UNos_maricones^#	WA	433ms	112260kb	C++14	2.0kb	2023-11-10 05:44:43	2023-11-10 05:44:44

Judging History

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

[2023-11-10 05:44:44]
评测

测评结果：WA
用时：433ms
内存：112260kb

查看

[2023-11-10 05:44:43]
提交

answer

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

#define ff first
#define ss second
#define pb push_back

typedef long long ll;
typedef pair <int,int> pii;

const int N = 185;
const int MAX_FACT = 362885;

int n, m;
vector <int> perm[N];
unordered_map <string, int> mp;
set <int> s;
string aux;

bool vis[MAX_FACT][N];
void get_cant (int id_perm, int ind, string &str ) {
    if ( vis[id_perm][ind] ) return;
    vis[id_perm][ind] = true;
    s.insert ( id_perm );
    if ( ind < 0 ) return;
    get_cant ( id_perm, ind-1, str );
    for ( int i = 0; i < n; ++i )
        aux[i] = perm[ind][str[i]-'1']+'0';
    id_perm = mp[aux];
    str = aux;
    get_cant ( id_perm, ind-1, str );
    return;
}

int checkPerm () {
    string bas_perm = "";
    for ( int i = 1; i <= n; ++i )
        bas_perm.pb ( i + '0' );
    int it = 0;
    do {
        mp[bas_perm] = it++;
    } while ( next_permutation ( bas_perm.begin(), bas_perm.end() ) );
    get_cant ( it, m-1, bas_perm );
    return s.size() - 1;
}

unordered_set <string> us;
int checkSubsets () {
    vector <int> curr_p ( n );
    for ( int mask = 1; mask < (1 << m); ++mask ) {
        for ( int i = 0; i < n; ++i )
            curr_p[i] = i+1;
        for ( int j = m-1; j >= 0; --j ) {
            if ( !((mask>>j)&1) ) continue;
            for ( int i = 0; i < n; ++i )
                curr_p[i] = perm[j][curr_p[i]-1];
        }
        string curr_str = "";
        for ( int i = 0; i < n; ++i )
            curr_str += curr_p[i] + '0';
        us.insert ( curr_str );
    }
    return us.size();
}

int main () {
        
    #ifndef LOCAL
    #endif

    scanf ( "%d%d", &n, &m );
    aux = string ( n, ' ' );
    for ( int i = 0; i < m; ++i ) {
        for ( int h = 0; h < n; ++h ) {
            int curr;
            scanf ( "%d", &curr );
            perm[i].pb ( curr );
        }
    }

    int res;
    if ( n <= 9 ) {
        res = checkPerm ();
    } else {
        res = checkSubsets ();
    }
    printf ( "%d\n", res );

    return 0;
}

源文件, 语言: C++14

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 4060kb

input:

output:

result:

ok 1 number(s): "8"

Test #2:

score: 0

Accepted

time: 0ms

memory: 4068kb

input:

2 1
2 1

output:

result:

ok 1 number(s): "1"

Test #3:

score: 0

Accepted

time: 0ms

memory: 4072kb

input:

output:

result:

ok 1 number(s): "1"

Test #4:

score: 0

Accepted

time: 0ms

memory: 3780kb

input:

180 1
52 71 167 89 165 102 119 125 9 128 180 24 48 172 108 22 164 28 159 111 30 91 67 51 136 97 126 133 177 65 115 157 114 11 171 178 23 127 163 103 99 18 56 94 176 77 44 1 124 74 61 87 4 40 63 92 169 84 146 6 88 55 152 49 10 90 43 174 70 50 69 154 73 147 110 20 82 59 112 12 64 143 16 138 5 170 155 ...

output:

result:

ok 1 number(s): "1"

Test #5:

score: 0

Accepted

time: 0ms

memory: 3860kb

input:

output:

result:

ok 1 number(s): "2"

Test #6:

score: 0

Accepted

time: 0ms

memory: 4076kb

input:

90 2
43 44 28 69 66 18 5 23 87 8 24 89 31 29 81 1 68 2 78 53 49 54 4 13 77 61 33 57 63 85 55 79 46 35 45 64 65 42 30 6 19 74 82 80 17 26 32 59 7 72 16 3 47 73 39 36 25 34 56 86 71 62 84 40 41 11 50 27 20 14 37 12 38 58 48 83 76 70 51 88 22 90 21 9 10 60 15 52 75 67
9 73 52 51 81 16 71 77 6 57 11 75 ...

output:

result:

ok 1 number(s): "3"

Test #7:

score: 0

Accepted

time: 0ms

memory: 3816kb

input:

output:

result:

ok 1 number(s): "6"

Test #8:

score: 0

Accepted

time: 0ms

memory: 3732kb

input:

60 3
35 38 36 43 59 60 20 16 8 51 58 18 33 26 44 7 41 27 39 9 37 48 25 40 30 14 21 13 5 1 19 11 3 28 57 47 17 56 45 34 12 49 29 32 55 24 31 50 42 22 53 23 4 15 2 46 6 10 52 54
41 49 10 55 3 38 35 29 6 26 2 46 58 39 24 47 51 25 44 37 42 43 20 53 60 12 40 17 28 13 27 57 15 52 8 22 11 14 59 21 48 9 32 ...

output:

result:

ok 1 number(s): "7"

Test #9:

score: 0

Accepted

time: 0ms

memory: 3800kb

input:

output:

result:

ok 1 number(s): "24"

Test #10:

score: 0

Accepted

time: 1ms

memory: 3788kb

input:

45 4
44 38 33 27 25 17 35 4 22 41 15 3 10 16 21 28 23 19 34 37 2 32 43 12 6 31 29 9 45 18 11 30 13 26 42 5 39 40 8 24 14 1 7 20 36
28 43 12 34 21 7 20 26 13 1 25 4 44 32 11 15 33 18 14 5 6 42 45 36 9 35 2 30 38 10 41 27 17 23 19 8 29 16 3 37 40 31 39 22 24
5 22 23 43 36 33 29 39 44 9 35 34 7 42 8 11...

output:

result:

ok 1 number(s): "15"

Test #11:

score: 0

Accepted

time: 1ms

memory: 3916kb

input:

18 10
13 4 18 16 1 8 17 6 14 2 10 12 5 9 3 11 15 7
1 7 15 13 12 2 17 18 16 11 9 8 6 14 3 4 10 5
1 9 3 4 6 14 5 10 12 13 7 8 16 2 15 17 18 11
2 10 16 3 17 8 4 13 12 11 5 7 14 9 1 15 18 6
7 9 4 14 10 2 17 6 8 16 1 13 12 5 11 18 15 3
13 4 16 10 5 2 9 1 11 3 18 8 6 12 15 14 7 17
9 14 18 17 2 12 16 10 15...

output:

result:

ok 1 number(s): "1023"

Test #12:

score: 0

Accepted

time: 74ms

memory: 21840kb

input:

10 18
9 6 4 8 3 7 10 1 2 5
10 9 8 3 5 6 1 2 7 4
8 2 5 4 9 3 1 7 6 10
10 5 2 8 1 6 4 7 9 3
2 3 5 4 10 9 6 8 7 1
6 7 8 10 5 3 4 1 9 2
10 6 4 2 1 5 3 8 9 7
6 8 9 1 2 4 5 3 7 10
7 6 3 1 5 9 2 10 4 8
10 5 7 4 9 1 2 6 3 8
5 4 6 9 3 7 8 1 2 10
5 9 8 2 7 1 3 10 6 4
5 2 10 3 7 1 4 6 9 8
1 10 2 6 5 7 8 9 3 4
...

output:

result:

ok 1 number(s): "252941"

Test #13:

score: 0

Accepted

time: 1ms

memory: 3980kb

input:

18 10
1 13 12 15 10 17 14 8 5 3 9 7 11 2 6 16 4 18
3 14 1 17 13 10 16 12 8 11 18 7 2 5 6 4 15 9
14 13 4 18 7 9 10 16 11 5 3 12 15 8 1 2 6 17
8 7 17 3 6 10 4 2 15 13 12 18 14 16 11 9 1 5
16 7 10 1 9 5 15 3 4 13 14 8 17 11 6 18 2 12
2 6 1 16 17 9 18 14 12 4 3 11 13 8 7 5 10 15
9 1 16 10 8 17 4 15 2 14...

output:

result:

ok 1 number(s): "1023"

Test #14:

score: 0

Accepted

time: 72ms

memory: 21676kb

input:

10 18
8 4 3 10 2 7 9 5 6 1
4 3 5 10 1 7 9 2 8 6
5 8 3 4 10 1 6 9 2 7
3 1 2 4 9 8 7 6 5 10
2 7 3 8 5 10 9 1 6 4
7 9 4 6 3 5 10 1 2 8
5 7 6 8 4 2 10 1 9 3
9 10 3 2 4 6 8 5 1 7
6 5 7 10 2 3 1 4 8 9
7 1 8 2 3 10 6 9 5 4
9 6 1 5 4 8 10 2 7 3
9 5 6 2 10 1 8 3 4 7
1 10 7 4 3 5 9 6 8 2
6 10 4 5 2 9 7 1 8 3
...

output:

result:

ok 1 number(s): "252421"

Test #15:

score: -100

Wrong Answer

time: 433ms

memory: 112260kb

input:

9 20
9 7 5 1 8 6 4 3 2
2 3 1 7 4 6 9 8 5
4 2 8 5 3 7 9 1 6
6 9 7 8 2 1 5 4 3
6 5 3 7 8 1 2 4 9
3 4 2 8 7 9 1 6 5
8 5 2 7 6 3 1 4 9
4 7 9 6 8 2 3 5 1
3 2 9 1 8 6 7 4 5
4 7 1 3 6 5 9 8 2
2 8 4 1 6 7 9 3 5
2 1 4 7 3 9 6 8 5
3 9 6 7 2 8 1 4 5
6 2 5 8 1 7 4 3 9
9 2 6 7 1 3 4 5 8
7 2 4 1 9 6 5 8 3
7 3 8 1...

output:

result:

wrong answer 1st numbers differ - expected: '342954', found: '328450'