# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1058016 | tolbi | Digital Circuit (IOI22_circuit) | C++17 | 3079 ms | 3160 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
constexpr int MOD = 1e9+2022;
vector<vector<int>> arr;
int N,M,P;
array<int,2> dp[200023];
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
::N=N,::M=M;
arr.resize(N);
for (int i = 1; i < N+M; i++){
arr[P[i]].push_back(i);
}
for (int i = N; i < N+M; i++){
dp[i][A[i-N]]=1;
dp[i][A[i-N]^1]=0;
}
}
int count_ways(int L, int R) {
for (int i = L; i <= R; i++){
swap(dp[i][0],dp[i][1]);
}
for (int i = N-1; i >= 0; i--){
vector<int> curdp(1,0);
curdp[0]=1;
for (int j = 0; j < arr[i].size(); j++){
vector<int> ndp(curdp.size()+1);
for (int k = 0; k < ndp.size(); k++){
if (k!=0){
ndp[k]=(1ll*curdp[k-1]*dp[arr[i][j]][1])%MOD;
if (ndp[k]>=MOD) ndp[k]-=MOD;
}
if (k!=curdp.size()){
ndp[k]+=(1ll*curdp[k]*dp[arr[i][j]][0])%MOD;
if (ndp[k]>=MOD) ndp[k]-=MOD;
}
}
swap(ndp,curdp);
}
dp[i][0]=dp[i][1]=0;
for (int j = 0; j < curdp.size(); j++){
dp[i][0]+=(1ll*(arr[i].size()-j)*curdp[j])%MOD;
dp[i][1]+=(1ll*j*curdp[j])%MOD;
if (dp[i][0]>=MOD) dp[i][0]-=MOD;
if (dp[i][1]>=MOD) dp[i][1]-=MOD;
}
}
return dp[0][1];
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |