Submission #1119037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119037		lam280407	Binaria (CCO23_day1problem1)	C++17	10 / 25	72 ms	10120 KiB

Main

#include<bits/stdc++.h>
#define int long long
#define vi vector<int>
#define pii pair<int, int>
#define fi first
#define se second
#define bit(n, i) ((n >> i) & 1)
#define all(x) (x).begin(), (x).end()
#define el '\n'
#define TASK "bai1"
using namespace std;
const int N = 1e6 + 6;
const int mode = 1e6 + 3;
int n, k, a[N];


namespace sub12{
    int ans = 0;
    void quay(string s){
        if (s.size() == n){
            s = '#' + s;
            int len = 0, sum = 0;
            for (int i = 1; i <= k; ++i) sum += (s[i] == '1');
            if (sum != a[++len]) return;
            for (int i = k + 1; i <= n; ++i){
                sum -= (s[i - k] == '1');
                sum += (s[i] == '1');
                if (sum != a[++len]) return;
            }
            ++ans;
            return;
        }
        quay(s + '0');
        quay(s + '1');
    }
    void init(){
        quay("");
        cout << ans % mode;
    }
}


namespace sub3{
    int dp[1003][1 << 10];
    void init(){
        int len = 1;
        for (int mask = 0; mask < (1 << k); ++mask){
            int bits = 0;
            for (int i = 0; i < k; ++i){
                if (bit(mask, i)) ++bits;
            }
            if (bits == a[len]) dp[k][mask] = 1;
        }
        for (int i = k + 1; i <= n; ++i){
            ++len;
            for (int mask = 0; mask < (1 << k); ++mask){
                int bits = 0;
                for (int i = 0; i < k; ++i){
                    if (bit(mask, i)) ++bits;
                }
                if (bits != a[len]) continue;
                int pre = mask;
                pre &= ~(1 << k - 1);
                pre <<= 1;
                dp[i][mask] += dp[i - 1][pre | 1];
                dp[i][mask] += dp[i - 1][pre];
            }
        }
        int ans = 0;
        for (int mask = 0; mask < (1 << k); ++mask) (ans += dp[n][mask]) %= mode;
        cout << ans;
    }
}


void solve(){
    cin >> n >> k;
    for (int i = 1; i <= n - k + 1; ++i) cin >> a[i];
    if (n <= 10) sub12::init();
    else if (n <= 1000 && k <= 10) sub3::init();
}


void file(){
    if (fopen(TASK".inp", "r")){
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
}


signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    file();
    solve();
}

Compilation message (stderr)

Main.cpp: In function 'void sub12::quay(std::string)':
Main.cpp:20:22: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   20 |         if (s.size() == n){
      |             ~~~~~~~~~^~~~
Main.cpp: In function 'void sub3::init()':
Main.cpp:63:33: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   63 |                 pre &= ~(1 << k - 1);
      |                               ~~^~~
Main.cpp: In function 'void file()':
Main.cpp:86:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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