Submission #1249641

#	Time	Username	Problem	Language	Result	Execution time	Memory
1249641		thanh3008	Cryptography (NOI20_crypto)	C++20	24 / 100	25 ms	7340 KiB

Crypto

#include <bits/stdc++.h>
#define TASK ""
#define fi first
#define se second
#define pb push_back
#define ll long long

using namespace std;
const int N=3e5+7,MOD=1e9+7;
ll n,a[N],b[N],giaithua[N],x[N],cnt=0;
bool tangdan=1,giamdan=1,kt[N],ok=0,kdau=1;

void backtrack(int pos){
    for(int i=1;i<=n;i++){
        if(!kt[i]){
            x[pos]=b[i];
            kt[i]=1;
            if(pos>=n){
                cnt++;
                if(cnt>=MOD) cnt-=MOD;
                ok=1;
                for(int i=1;i<=n;i++){
                    if(a[i]!=x[i]){
                        ok=0;
                        break;
                    }
                }
                if(ok){
                    cout<<cnt<<"\n";
                    return;
                }
            }
            else backtrack(pos+1);
            kt[i]=0;
        }
    }
}

int main(){
    if(fopen(TASK".inp","r")){
        freopen(TASK".inp","r",stdin);
        freopen(TASK".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    giaithua[0]=1;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=a[i];
        giaithua[i]=(giaithua[i-1]*i)%MOD;
    }
    for(int i=1;i<n;i++){
        if(a[i]>a[i+1]){
            tangdan=0;
            break;
        }
    }
    for(int i=1;i<n;i++){
        if(a[i]<a[i+1]){
            giamdan=0;
            break;
        }
    }
    if(tangdan){
        cout<<"1\n";
        return 0;
    }
    else if(giamdan){
        cout<<giaithua[n]<<"\n";
        return 0;
    }
    if(a[1]<a[2]) kdau=0;
    for(int i=2;i<n;i++){
        if(a[i]>a[i+1]){
            kdau=0;
            break;
        }
    }
    if(kdau){
        ll res=0;
        for(int i=1;i<=(a[1]-1);i++) res=(res+giaithua[n-1])%MOD;
        cout<<res<<"\n";
        return 0;
    }
    if(n<=8){
        sort(b+1,b+n+1);
        backtrack(1);
    }

    return 0;
}

Compilation message (stderr)

Crypto.cpp: In function 'int main()':
Crypto.cpp:41:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         freopen(TASK".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Crypto.cpp:42:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         freopen(TASK".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 9 / 9
• Subtask 3: 10 / 10
• Subtask 4: 0 / 11
• Subtask 5: 0 / 21
• Subtask 6: 0 / 13
• Subtask 7: 0 / 19
• Subtask 8: 0 / 12