QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#264669	#7687. Randias Permutation Task	qkm66666^#	WA	171ms	19436kb	C++17	2.7kb	2023-11-25 14:49:20	2023-11-25 14:49:20

Judging History

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

[2023-11-25 14:49:20]
评测

测评结果：WA
用时：171ms
内存：19436kb

查看

[2023-11-25 14:49:20]
提交

answer

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cassert>
#include<cstdio>
#include<cctype>
#include<vector>
#include<bitset>
#include<random>
#include<ctime>
#include<queue>
#include<cmath>
#include<list>
#include<map>
#include<set>
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define pll pair<long long,long long>
#define FF fflush(stdout)
#define inf 0x3f3f3f3f
#define endl "\n"
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
//char buf[1<<20],*p1,*p2;
//#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
inline int read()
{
    int s=0,f=1;
    char x=getchar();
    while(!isdigit(x))f=(x=='-'?-1:1),x=getchar();
    while(isdigit(x))s=s*10+x-'0',x=getchar();
    return s*f;
}
const int p=1e9+7;
//ll ksm(int a,int b){ll ans=1,bs=a;while(b){if(b&1)ans=ans*bs%p;bs=bs*bs%p;b>>=1;}return ans;}
mt19937 rd(time(0));
#define reaD read
int n,m;
int ans=0;
int a[181][181];
int b[181];
map<ull,bool> M;
int c[181];
void cov(int *a,int *b)
{
    for(int i=1;i<=n;i++)
    c[i]=a[b[i]];
    for(int i=1;i<=n;i++)
    a[i]=c[i];
    return ;
}
void cov2(vector<int> &a,int *b)
{
    vector<int> c;
    for(int i=0;i<n;i++)
    {
        c.pb(a[b[i+1]-1]);
    }
    a=c;
    return ;
}
void sol1()
{
    for(int i=1;i<(1<<m);i++)
    {
        for(int j=1;j<=n;j++)
        b[j]=j;
        for(int j=0;j<m;j++)
        if((1<<j)&i)
        {
            cov(b,a[j]);
        }
        ull w=0;
        for(int j=1;j<=n;j++)
        w=(w*131+b[j])%p;
        if(M.find(w)==M.end())
        {
            // for(int j=1;j<=n;j++)
            // printf("%d ",b[j]);puts("");
            ans++,M[w]=1;
        }
    }
    return ;
}
map<vector<int>,bool> f[182];
void sol2()
{
    vector<int> w;
    for(int i=1;i<=n;i++)
    w.pb(a[0][i]);
    f[0][w]=1;
    for(int i=1;i<m;i++)
    {
        f[i]=f[i-1];
        vector<int> w;
        for(int j=1;j<=n;j++)
        w.pb(a[i][j]);
        f[i][w]=1;
        for(auto j:f[i-1])
        {
            vector<int> o=j.fi;
            cov2(o,a[i]);
            f[i][o]=1;
        }
    }
    for(auto i:f[m-1])
    {
        // for(auto j:i.fi)cout<<j<<" ";
        // puts("");
        ans++;
    }
    
    return ;
}
int main()
{
    n=read(),m=reaD();
    for(int i=0;i<m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            a[i][j]=reaD();
        }
    }
    if(m<=20)sol1();
    // printf("%d\n",ans);ans=0;
    else sol2();
    printf("%d",ans);
    // system("pause");
    return 0;
}

源文件, 语言: C++17

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 3716kb

input:

output:

result:

ok 1 number(s): "8"

Test #2:

score: 0

Accepted

time: 1ms

memory: 3688kb

input:

2 1
2 1

output:

result:

ok 1 number(s): "1"

Test #3:

score: 0

Accepted

time: 1ms

memory: 3776kb

input:

output:

result:

ok 1 number(s): "1"

Test #4:

score: 0

Accepted

time: 1ms

memory: 3628kb

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: 1ms

memory: 3708kb

input:

output:

result:

ok 1 number(s): "2"

Test #6:

score: 0

Accepted

time: 0ms

memory: 3680kb

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: 1ms

memory: 3712kb

input:

output:

result:

ok 1 number(s): "6"

Test #8:

score: 0

Accepted

time: 0ms

memory: 3636kb

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: 1ms

memory: 3804kb

input:

output:

result:

ok 1 number(s): "24"

Test #10:

score: 0

Accepted

time: 1ms

memory: 3640kb

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: 3760kb

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: -100

Wrong Answer

time: 171ms

memory: 19436kb

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:

wrong answer 1st numbers differ - expected: '252941', found: '252914'