oj.uz

Submission #504846

# Submission time Handle Problem Language Result Execution time Memory
504846 2022-01-10T09:11:12 Z ToroTN Cryptography (NOI20_crypto) C++14
0 / 100
 4 ms 2636 KB 
#include<bits/stdc++.h>
using namespace std;
long long n,a[300005],b[300005],fac[300005],fen[300005],c[300005],ans=0;
vector<long long> v;
map<long long,long long> mp;
void update(long long u,long long val)
{
    while(u<=n)
    {
        fen[u]+=val;
        fen[u]%=1000000007;
        u+=(u&(-u));
    }
}
long long query(long long u)
{
    long long val=0;
    while(u>=1)
    {
        val+=fen[u];
        val%=1000000007;
        u-=(u&(-u));
    }
    return val;
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
        v.push_back(a[i]);
    }
    v.push_back(-1);
    sort(v.begin(),v.end());
    for(int i=1;i<=n;i++)
    {
        mp[v[i]]=i;
    }
    for(int i=1;i<=n;i++)
    {
        b[i]=mp[a[i]];
    }
    for(int i=1;i<=n;i++)
    {
        printf("%lld ",b[i]);
    }
    printf("\n");
    fac[0]=1;
    for(int i=1;i<=300000;i++)
    {
        fac[i]=fac[i-1]*i;
        fac[i]%=1000000007;
    }
    for(int i=n;i>=1;i--)
    {
        update(b[i],1);
        c[i]=query(b[i]);
    }
    for(int i=1;i<=n;i++)
    {
        printf("%lld ",c[i]);
    }
    printf("\n");
    for(int i=1;i<=n;i++)
    {
        ans+=(c[i]-1)*fac[n-i];
        ans%=1000000007;
    }
    printf("%lld\n",(ans+1)%1000000007);
}

Compilation message

Crypto.cpp: In function 'int main()':
Crypto.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |     scanf("%lld",&n);
      |     ~~~~~^~~~~~~~~~~
Crypto.cpp:31:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |         scanf("%lld",&a[i]);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2636 KB Output isn't correct
2 Halted 0 ms 0 KB -