Submission #1273887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1273887		phtung	Binaria (CCO23_day1problem1)	C++20	25 / 25	56 ms	16096 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define name "IO"
#define int long long 

const int inf = 1e18 + 7; 
const int maxn = 1e6 + 5;
const int mod = 1e6 + 3; 
int n, k, a[maxn]; 

int Pow(int x, int y) 
{
    int ans = 1;
    while (y > 0) 
    {
        if (y & 1) ans = (ans * x) % mod;
        y /= 2;
        x = x * x;
        x %= mod; 
    }
    return ans;
}

void solve()
{
    cin >> n >> k;
    for(int i = 1; i <= n - k + 1; i++) cin >> a[i];
    
    if(n - k + 1 == 0)
    {
        cout << 0 << "\n";
        return; 
    }

    int m = n - k + 1; 

    vector<int> d(m); 
    for(int i = 1; i < m; i++) d[i] = a[i + 1] - a[i]; 

    int zero = 0, one = 0, free = 0; 

    for(int r = 1; r <= k; r++)
    {
        int pos = r; 
        int c = 0; 

        bool ok = 1;
        bool posi = 0, neg = 0; 

        while(pos <= n - k)
        {
            c += d[pos];
            pos += k;
            if(abs(c) >= 2) 
            {
                ok = 0;
                break; 
            }
            if(c == 1) posi = 1; 
            if(c == -1) neg = 1;    
        }

        if(!ok)
        {
            cout << 0 << "\n";
            return; 
        }

        if(posi && neg)
        {
            cout << 0 << "\n";
            return; 
        }

        if(posi) zero++; 
        else if(neg) one++; 
        else free++; 
    }

    int need = a[1] - one; 
    if(need < 0 || need > free)
    {
        cout << 0 << "\n";
        return; 
    }

    int N = free, K = need; 
    vector<int> fac(N + 1, 1), inv_fac(N + 1, 1); 
    for(int i = 1; i <= N; i++) fac[i] = (fac[i - 1] * i) % mod; 
    inv_fac[N] = Pow(fac[N], mod - 2); 
    for(int i = N - 1; i >= 0; i--) inv_fac[i] = (inv_fac[i + 1] * (i + 1)) % mod;
    
    int res = fac[N] * inv_fac[K] % mod * inv_fac[N - K] % mod; 
    cout << res << "\n"; 
}

signed main()
{
    if (fopen (name".INP", "r"))
    {
        freopen (name".INP", "r", stdin);
        freopen (name".OUT", "w", stdout);
    }

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    clock_t start = clock(); 

    int t = 1;

    while(t--) solve(); 

    std::cerr << "Time: " << clock() - start << "ms\n";

    return 0; 

}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:103:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  103 |         freopen (name".INP", "r", stdin);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:104:17: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         freopen (name".OUT", "w", stdout);
      |         ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 4 / 4
• Subtask 4: 4 / 4
• Subtask 5: 4 / 4
• Subtask 6: 7 / 7