oj.uz

Submission #930194

# Submission time Handle Problem Language Result Execution time Memory
930194 2024-02-18T23:50:05 Z Edu175 Digital Circuit (IOI22_circuit) C++17
16 / 100
 637 ms 19568 KB 
#include "circuit.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ioi=b;i<ioi;i++)
#define dfore(i,a,b) for(ll i=b-1,ioi=a;i>=ioi;i--)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) for(auto djfhg:v)cout<<djfhg<<" ";cout<<"\n"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
const ll MAXN=2e5+5,MOD=1000002022;
int add(int a, int b){a+=b;if(a>=MOD)a-=MOD;return a;}
int sub(int a, int b){a-=b;if(a<0)a+=MOD;return a;}
int mul(ll a, ll b){return a*b%MOD;}

ll n,m;
vector<ll>g[MAXN];
ll a[MAXN],tot[MAXN],dp[MAXN];
struct tn{
	ll r0,r1;
};
/*string cv(tn a){
	return "["+to_string(a.r0)+","+to_string(a.r1)+"]";
}*/
tn unit(ll v){
	if(!v)return tn({1,0});
	return tn({0,1});
}
typedef ll tl;
tl CLEAR=0;
tn NEUT({0,0});
tn oper(tn a, tn b, ll k){
	tn c=NEUT;
	ll xa=2*k-1,xb=2*k;
	c.r0=add(mul(a.r0,tot[xb]),mul(b.r0,tot[xa]));
	c.r1=add(mul(a.r1,tot[xb]),mul(b.r1,tot[xa]));
	return c;
}
void acum(tl &a, ll v){
	a^=v;
};
void calc(tn &a, ll v){
	if(v)swap(a.r0,a.r1);
}
struct STree{
	vector<tn>st; vector<tl>lazy; ll n;
	STree(ll n): st(4*n+5,NEUT),lazy(4*n+5,CLEAR),n(n){}
	void push(ll k, ll s, ll e){
		calc(st[k],lazy[k]);
		if(e-s>1){
			acum(lazy[2*k],lazy[k]);
			acum(lazy[2*k+1],lazy[k]);
		}
		lazy[k]=CLEAR;
	}
	void init(ll k, ll s, ll e, vector<int>&a){
		if(e-s==1)st[k]=unit(a[s]);
		else {
			ll m=(s+e)/2;
			init(2*k,s,m,a); init(2*k+1,m,e,a);
			st[k]=oper(st[2*k],st[2*k+1],k);
		}
		//cout<<"init "<<k<<" "<<s<<","<<e<<" = "<<cv(st[k])<<"\n";
	}
	void upd(ll k, ll s, ll e, ll a, ll b){
		push(k,s,e);
		if(e<=a||b<=s);
		else if(a<=s&&e<=b){
			acum(lazy[k],1);
			push(k,s,e);
		}
		else {
			ll m=(s+e)/2;
			upd(2*k,s,m,a,b); upd(2*k+1,m,e,a,b);
			st[k]=oper(st[2*k],st[2*k+1],k);
		}
		//cout<<"upd "<<k<<" "<<s<<","<<e<<" "<<a<<","<<b<<" = "<<cv(st[k])<<"\n";
	}
	void init(vector<int>&a){init(1,0,n,a);}
	void upd(ll a, ll b){upd(1,0,n,a,b);}
	ll get(){
		push(1,0,n);
		return st[1].r1;
	}
};
STree st(0);
void init(int N, int M, std::vector<int> P, std::vector<int> A){
	n=N,m=M;
	fore(i,0,SZ(P)){
		if(P[i]!=-1)g[P[i]].pb(i);
	}
	fore(i,0,m)tot[n+i]=1;
	dfore(x,0,n){
		ll k=SZ(g[x]);
		tot[x]=k;
		for(auto y:g[x])tot[x]=mul(tot[x],tot[y]);
	}
	st=STree(m);
	st.init(A);
}

int count_ways(int L, int R){
	ll l=L-n,r=R-n+1;
	//cout<<"cw "<<l<<","<<r<<":\n";
	//fore(i,1,n+m)cout<<i<<": "<<cv(st.st[i])<<"\n";
	st.upd(l,r);
	return st.get();
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7512 KB Output is correct
3 Incorrect 2 ms 7512 KB 1st lines differ - on the 1st token, expected: '509', found: '24'
4 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7512 KB Output is correct
3 Correct 2 ms 7768 KB Output is correct
4 Correct 2 ms 7512 KB Output is correct
5 Correct 2 ms 7512 KB Output is correct
6 Incorrect 2 ms 7512 KB 1st lines differ - on the 1st token, expected: '706880838', found: '293324902'
7 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7512 KB Output is correct
3 Incorrect 2 ms 7512 KB 1st lines differ - on the 1st token, expected: '509', found: '24'
4 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 12356 KB Output is correct
2 Correct 566 ms 19392 KB Output is correct
3 Correct 616 ms 19392 KB Output is correct
4 Correct 599 ms 19400 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 383 ms 12356 KB Output is correct
2 Correct 566 ms 19392 KB Output is correct
3 Correct 616 ms 19392 KB Output is correct
4 Correct 599 ms 19400 KB Output is correct
5 Correct 493 ms 12356 KB Output is correct
6 Correct 637 ms 19384 KB Output is correct
7 Correct 620 ms 19384 KB Output is correct
8 Correct 634 ms 19568 KB Output is correct
9 Correct 249 ms 7768 KB Output is correct
10 Correct 599 ms 8212 KB Output is correct
11 Correct 563 ms 8212 KB Output is correct
12 Correct 513 ms 8212 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7512 KB Output is correct
3 Correct 2 ms 7768 KB Output is correct
4 Correct 2 ms 7512 KB Output is correct
5 Correct 2 ms 7512 KB Output is correct
6 Incorrect 2 ms 7512 KB 1st lines differ - on the 1st token, expected: '706880838', found: '293324902'
7 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7512 KB Output is correct
3 Incorrect 2 ms 7512 KB 1st lines differ - on the 1st token, expected: '509', found: '24'
4 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7512 KB Output is correct
2 Correct 2 ms 7512 KB Output is correct
3 Incorrect 2 ms 7512 KB 1st lines differ - on the 1st token, expected: '509', found: '24'
4 Halted 0 ms 0 KB -