Submission #1230438

#TimeUsernameProblemLanguageResultExecution timeMemory
1230438MalixDigital Circuit (IOI22_circuit)C++20
18 / 100
3076 ms2162688 KiB
#include "circuit.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vii; typedef pair<int,int> pi; typedef vector<pi> pii; typedef tuple<ll,int,int> ti; typedef vector<ll> li; typedef vector<li> lii; #define REP(i,a,b) for(int i=a;i<b;i++) #define F first #define S second #define PB push_back #define LSOne(s) ((s)&(-s)) #define all(x) (x).begin(),(x).end() ll INF=1000000000000000010; int inf=1e9+10; ll M=1000002022; int n,m; vi a,p,ch; void init(int N, int M, std::vector<int> P, std::vector<int> A) { n=N;m=M;a=A;p=P; ch.resize(n+m,0); REP(i,1,n+m)ch[p[i]]++; return; } int count_ways(int L, int R) { vector<vector<ll>> dp(n+m,vector<ll>(n+m,0)),dp2(n+m,vector<ll>(2,0)); REP(i,L-n,R-n+1)a[i]=1-a[i]; REP(i,n,n+m)dp2[i][a[i-n]]++; REP(i,0,n)dp[i][0]=1; for(int i=n+m-1;i>=0;i--){ int x=ch[i]; vector<ll> b=dp[i],c=dp[i]; REP(j,1,x+1){ b[j]+=b[j-1]; b[j]%=M; } for(int j=x-1;j>=0;j--){ c[j]+=c[j+1]; c[j]%=M; } REP(j,0,x+1){ if(j!=0)dp2[i][1]+=c[j]; if(j!=x)dp2[i][0]+=b[j]; dp2[i][1]%=M; dp2[i][0]%=M; } if(i==0)break; int k=p[i]; for(int j=n+m-1;j>=0;j--){ if(j!=n+m-1){ dp[k][j+1]+=dp[k][j]*dp2[i][1]; dp[k][j+1]%=M; } dp[k][j]*=dp2[i][0]; dp[k][j]%=M; } } return (int)dp2[0][1]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...