oj.uz

Submission #955243

# Submission time Handle Problem Language Result Execution time Memory
955243 2024-03-29T23:03:41 Z StefanSebez Digital Circuit (IOI22_circuit) C++17
9 / 100
 476 ms 20816 KB 
#include "circuit.h"
#include<bits/stdc++.h>
#include <vector>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int N=1e5+50;
const ll mod=1000002022;
ll Puta(ll a,ll b){a%=mod,b%=mod;ll x=a*b;x%=mod;return x;}
ll Plus(ll a,ll b){a%=mod,b%=mod;ll x=a+b;x%=mod;return x;}
vector<int>E[N];
int a[N],n,m,P[2*N];
ll res[N],dp[N][2],F[N];
/*void DFSsetup(int u){
	F[u]=E[u].size()+1;
	for(auto i:E[u]){
		DFSsetup(i);
		F[u]*=F[i];
	}
}*/
void DFS(int u){
	if(E[u].empty()) return;
	for(auto i:E[u]){
		DFS(i);
	}
	dp[u][1]=dp[u][0]=0;
	int mask=0;
	while(mask< 1<<(E[u].size())){
		ll temp1=1,sum=0;
		for(int i=0,temp=mask;i<E[u].size();i++,temp/=2){
			temp1=Puta(temp1,dp[E[u][i]][temp%2]);sum+=temp%2;
		}
		if(mask!=0) dp[u][1]=Plus(dp[u][1],Puta(sum,temp1));
		dp[u][0]=Plus(dp[u][0],Puta(E[u].size()-sum,temp1));
		mask++;
	}
	//dp[u][0]=F[u]-dp[u][1];
}
void Update(int v){
	dp[v][1]=1-dp[v][1];
	dp[v][0]=1-dp[v][0];
	int u=P[v];
	while(u!=-1){
		dp[u][1]=dp[u][0]=0;
		int mask=0;
		while(mask< 1<<(E[u].size())){
			ll temp1=1,sum=0;
			for(int i=0,temp=mask;i<E[u].size();i++,temp/=2){
				temp1=Puta(temp1,dp[E[u][i]][temp%2]);sum+=temp%2;
			}
			if(mask!=0) dp[u][1]=Plus(dp[u][1],Puta(sum,temp1));
			dp[u][0]=Plus(dp[u][0],Puta(E[u].size()-sum,temp1));
			mask++;
		}
		u=P[u];
	}
}
void init(int N1, int M1, std::vector<int> P1, std::vector<int> A) {
	n=N1,m=M1;
	for(int i=0;i<P1.size();i++) P[i]=P1[i];
	for(int i=0;i<P1.size();i++){
		E[P[i]].pb(i);
	}
	for(int i=0;i<m;i++){
		dp[n+i][1]=A[i],dp[n+i][0]=1-A[i];
		a[i]=A[i];
	}
	//DFSsetup(0);
	DFS(0);
	/*for(int i=0;i<=n+m-1;i++){
		printf("%i: %i %i\n",i,dp[i][0],dp[i][1]);
	}*/
	/*for(int i=1;i<=M;i++){

	}*/
}

int count_ways(int L, int R) {
	if(n==1){
		int ct=0;
		for(int i=L;i<=R;i++) a[i-1]=1-a[i-1];
		for(int i=0;i<=m-1;i++) ct+=a[i];
		return ct;
	}
	if(L==R){
		Update(L);
		return dp[0][1];
	}
	for(int i=L;i<=R;i++){
		dp[i][1]=1-dp[i][1];
		dp[i][0]=1-dp[i][0];
	}
	DFS(0);
	/*for(int i=0;i<=n+m-1;i++){
		printf("%i: %i %i\n",i,dp[i][0],dp[i][1]);
	}*/
	return dp[0][1];
}

Compilation message

circuit.cpp: In function 'void DFS(int)':
circuit.cpp:32:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |   for(int i=0,temp=mask;i<E[u].size();i++,temp/=2){
      |                         ~^~~~~~~~~~~~
circuit.cpp: In function 'void Update(int)':
circuit.cpp:50:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |    for(int i=0,temp=mask;i<E[u].size();i++,temp/=2){
      |                          ~^~~~~~~~~~~~
circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:62:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for(int i=0;i<P1.size();i++) P[i]=P1[i];
      |              ~^~~~~~~~~~
circuit.cpp:63:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for(int i=0;i<P1.size();i++){
      |              ~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6912 KB Output is correct
3 Correct 18 ms 6744 KB Output is correct
4 Correct 2 ms 6744 KB Output is correct
5 Correct 2 ms 6744 KB Output is correct
6 Correct 3 ms 6744 KB Output is correct
7 Correct 4 ms 6744 KB Output is correct
8 Correct 2 ms 6744 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 2 ms 6996 KB Output is correct
3 Correct 2 ms 6920 KB Output is correct
4 Correct 2 ms 6744 KB Output is correct
5 Correct 2 ms 6744 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 2 ms 6744 KB Output is correct
8 Correct 2 ms 6744 KB Output is correct
9 Correct 3 ms 6744 KB Output is correct
10 Correct 2 ms 7000 KB Output is correct
11 Correct 2 ms 7000 KB Output is correct
12 Correct 2 ms 6744 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6912 KB Output is correct
3 Correct 18 ms 6744 KB Output is correct
4 Correct 2 ms 6744 KB Output is correct
5 Correct 2 ms 6744 KB Output is correct
6 Correct 3 ms 6744 KB Output is correct
7 Correct 4 ms 6744 KB Output is correct
8 Correct 2 ms 6744 KB Output is correct
9 Correct 1 ms 6744 KB Output is correct
10 Correct 2 ms 6996 KB Output is correct
11 Correct 2 ms 6920 KB Output is correct
12 Correct 2 ms 6744 KB Output is correct
13 Correct 2 ms 6744 KB Output is correct
14 Correct 2 ms 6744 KB Output is correct
15 Correct 2 ms 6744 KB Output is correct
16 Correct 2 ms 6744 KB Output is correct
17 Correct 3 ms 6744 KB Output is correct
18 Correct 2 ms 7000 KB Output is correct
19 Correct 2 ms 7000 KB Output is correct
20 Correct 2 ms 6744 KB Output is correct
21 Correct 4 ms 6744 KB Output is correct
22 Correct 2 ms 6744 KB Output is correct
23 Correct 2 ms 6744 KB Output is correct
24 Correct 3 ms 6744 KB Output is correct
25 Correct 3 ms 6740 KB Output is correct
26 Correct 4 ms 6744 KB Output is correct
27 Correct 3 ms 6744 KB Output is correct
28 Correct 3 ms 6832 KB Output is correct
29 Correct 3 ms 6744 KB Output is correct
30 Correct 2 ms 6744 KB Output is correct
31 Correct 2 ms 6744 KB Output is correct
32 Correct 2 ms 6744 KB Output is correct
33 Correct 2 ms 6744 KB Output is correct
34 Correct 3 ms 6744 KB Output is correct
35 Incorrect 2 ms 6756 KB 1st lines differ - on the 1st token, expected: '235989424', found: '0'
36 Halted 0 ms 0 KB -

Subtask #4
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 8588 KB Output is correct
2 Runtime error 29 ms 20816 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 476 ms 8588 KB Output is correct
2 Runtime error 29 ms 20816 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 2 ms 6996 KB Output is correct
3 Correct 2 ms 6920 KB Output is correct
4 Correct 2 ms 6744 KB Output is correct
5 Correct 2 ms 6744 KB Output is correct
6 Correct 2 ms 6744 KB Output is correct
7 Correct 2 ms 6744 KB Output is correct
8 Correct 2 ms 6744 KB Output is correct
9 Correct 3 ms 6744 KB Output is correct
10 Correct 2 ms 7000 KB Output is correct
11 Correct 2 ms 7000 KB Output is correct
12 Correct 2 ms 6744 KB Output is correct
13 Correct 476 ms 8588 KB Output is correct
14 Runtime error 29 ms 20816 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6912 KB Output is correct
3 Correct 18 ms 6744 KB Output is correct
4 Correct 2 ms 6744 KB Output is correct
5 Correct 2 ms 6744 KB Output is correct
6 Correct 3 ms 6744 KB Output is correct
7 Correct 4 ms 6744 KB Output is correct
8 Correct 2 ms 6744 KB Output is correct
9 Correct 1 ms 6744 KB Output is correct
10 Correct 2 ms 6996 KB Output is correct
11 Correct 2 ms 6920 KB Output is correct
12 Correct 2 ms 6744 KB Output is correct
13 Correct 2 ms 6744 KB Output is correct
14 Correct 2 ms 6744 KB Output is correct
15 Correct 2 ms 6744 KB Output is correct
16 Correct 2 ms 6744 KB Output is correct
17 Correct 3 ms 6744 KB Output is correct
18 Correct 2 ms 7000 KB Output is correct
19 Correct 2 ms 7000 KB Output is correct
20 Correct 2 ms 6744 KB Output is correct
21 Correct 4 ms 6744 KB Output is correct
22 Correct 2 ms 6744 KB Output is correct
23 Correct 2 ms 6744 KB Output is correct
24 Correct 3 ms 6744 KB Output is correct
25 Correct 3 ms 6740 KB Output is correct
26 Correct 4 ms 6744 KB Output is correct
27 Correct 3 ms 6744 KB Output is correct
28 Correct 3 ms 6832 KB Output is correct
29 Correct 3 ms 6744 KB Output is correct
30 Correct 2 ms 6744 KB Output is correct
31 Correct 2 ms 6744 KB Output is correct
32 Correct 2 ms 6744 KB Output is correct
33 Correct 2 ms 6744 KB Output is correct
34 Correct 3 ms 6744 KB Output is correct
35 Incorrect 2 ms 6756 KB 1st lines differ - on the 1st token, expected: '235989424', found: '0'
36 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6744 KB Output is correct
2 Correct 1 ms 6912 KB Output is correct
3 Correct 18 ms 6744 KB Output is correct
4 Correct 2 ms 6744 KB Output is correct
5 Correct 2 ms 6744 KB Output is correct
6 Correct 3 ms 6744 KB Output is correct
7 Correct 4 ms 6744 KB Output is correct
8 Correct 2 ms 6744 KB Output is correct
9 Correct 1 ms 6744 KB Output is correct
10 Correct 2 ms 6996 KB Output is correct
11 Correct 2 ms 6920 KB Output is correct
12 Correct 2 ms 6744 KB Output is correct
13 Correct 2 ms 6744 KB Output is correct
14 Correct 2 ms 6744 KB Output is correct
15 Correct 2 ms 6744 KB Output is correct
16 Correct 2 ms 6744 KB Output is correct
17 Correct 3 ms 6744 KB Output is correct
18 Correct 2 ms 7000 KB Output is correct
19 Correct 2 ms 7000 KB Output is correct
20 Correct 2 ms 6744 KB Output is correct
21 Correct 4 ms 6744 KB Output is correct
22 Correct 2 ms 6744 KB Output is correct
23 Correct 2 ms 6744 KB Output is correct
24 Correct 3 ms 6744 KB Output is correct
25 Correct 3 ms 6740 KB Output is correct
26 Correct 4 ms 6744 KB Output is correct
27 Correct 3 ms 6744 KB Output is correct
28 Correct 3 ms 6832 KB Output is correct
29 Correct 3 ms 6744 KB Output is correct
30 Correct 2 ms 6744 KB Output is correct
31 Correct 2 ms 6744 KB Output is correct
32 Correct 2 ms 6744 KB Output is correct
33 Correct 2 ms 6744 KB Output is correct
34 Correct 3 ms 6744 KB Output is correct
35 Incorrect 2 ms 6756 KB 1st lines differ - on the 1st token, expected: '235989424', found: '0'
36 Halted 0 ms 0 KB -