oj.uz

Submission #955246

# Submission time Handle Problem Language Result Execution time Memory
955246 2024-03-29T23:22:49 Z StefanSebez Digital Circuit (IOI22_circuit) C++17
13 / 100
 3000 ms 14504 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+500;
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[2*N+500];
int a[N+500],n,m,P[2*N+500];
ll res[N+500],dp[2*N+500][2],F[N+500];
/*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;
	}
	for(int i=L;i<=R;i++){
		Update(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:30:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for(int i=0,temp=mask;i<E[u].size();i++,temp/=2){
      |                         ~^~~~~~~~~~~~
circuit.cpp: In function 'void Update(int)':
circuit.cpp:48:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |    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:60:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |  for(int i=0;i<P1.size();i++) P[i]=P1[i];
      |              ~^~~~~~~~~~
circuit.cpp:61:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |  for(int i=0;i<P1.size();i++){
      |              ~^~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 19 ms 8880 KB Output is correct
4 Correct 3 ms 8792 KB Output is correct
5 Correct 3 ms 8792 KB Output is correct
6 Correct 3 ms 8792 KB Output is correct
7 Correct 3 ms 8792 KB Output is correct
8 Correct 3 ms 8792 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 3 ms 8892 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 3 ms 8792 KB Output is correct
6 Correct 2 ms 8792 KB Output is correct
7 Correct 3 ms 8792 KB Output is correct
8 Correct 3 ms 8792 KB Output is correct
9 Correct 4 ms 8916 KB Output is correct
10 Correct 81 ms 8792 KB Output is correct
11 Correct 152 ms 8944 KB Output is correct
12 Correct 2 ms 8792 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 19 ms 8880 KB Output is correct
4 Correct 3 ms 8792 KB Output is correct
5 Correct 3 ms 8792 KB Output is correct
6 Correct 3 ms 8792 KB Output is correct
7 Correct 3 ms 8792 KB Output is correct
8 Correct 3 ms 8792 KB Output is correct
9 Correct 2 ms 8792 KB Output is correct
10 Correct 2 ms 8792 KB Output is correct
11 Correct 3 ms 8892 KB Output is correct
12 Correct 2 ms 8792 KB Output is correct
13 Correct 3 ms 8792 KB Output is correct
14 Correct 2 ms 8792 KB Output is correct
15 Correct 3 ms 8792 KB Output is correct
16 Correct 3 ms 8792 KB Output is correct
17 Correct 4 ms 8916 KB Output is correct
18 Correct 81 ms 8792 KB Output is correct
19 Correct 152 ms 8944 KB Output is correct
20 Correct 2 ms 8792 KB Output is correct
21 Correct 530 ms 8876 KB Output is correct
22 Correct 2 ms 8792 KB Output is correct
23 Correct 3 ms 8792 KB Output is correct
24 Correct 3 ms 8792 KB Output is correct
25 Correct 48 ms 8792 KB Output is correct
26 Correct 139 ms 8792 KB Output is correct
27 Correct 53 ms 8792 KB Output is correct
28 Correct 170 ms 8792 KB Output is correct
29 Correct 3 ms 8792 KB Output is correct
30 Correct 3 ms 8804 KB Output is correct
31 Correct 2 ms 8792 KB Output is correct
32 Correct 5 ms 8792 KB Output is correct
33 Correct 6 ms 8792 KB Output is correct
34 Correct 13 ms 8888 KB Output is correct
35 Incorrect 2 ms 8792 KB 1st lines differ - on the 1st token, expected: '235989424', found: '0'
36 Halted 0 ms 0 KB -

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 10712 KB Output is correct
2 Correct 790 ms 14484 KB Output is correct
3 Correct 774 ms 14504 KB Output is correct
4 Correct 713 ms 14424 KB Output is correct

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 10712 KB Output is correct
2 Correct 790 ms 14484 KB Output is correct
3 Correct 774 ms 14504 KB Output is correct
4 Correct 713 ms 14424 KB Output is correct
5 Execution timed out 3084 ms 10544 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 3 ms 8892 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 3 ms 8792 KB Output is correct
6 Correct 2 ms 8792 KB Output is correct
7 Correct 3 ms 8792 KB Output is correct
8 Correct 3 ms 8792 KB Output is correct
9 Correct 4 ms 8916 KB Output is correct
10 Correct 81 ms 8792 KB Output is correct
11 Correct 152 ms 8944 KB Output is correct
12 Correct 2 ms 8792 KB Output is correct
13 Correct 473 ms 10712 KB Output is correct
14 Correct 790 ms 14484 KB Output is correct
15 Correct 774 ms 14504 KB Output is correct
16 Correct 713 ms 14424 KB Output is correct
17 Execution timed out 3084 ms 10544 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 19 ms 8880 KB Output is correct
4 Correct 3 ms 8792 KB Output is correct
5 Correct 3 ms 8792 KB Output is correct
6 Correct 3 ms 8792 KB Output is correct
7 Correct 3 ms 8792 KB Output is correct
8 Correct 3 ms 8792 KB Output is correct
9 Correct 2 ms 8792 KB Output is correct
10 Correct 2 ms 8792 KB Output is correct
11 Correct 3 ms 8892 KB Output is correct
12 Correct 2 ms 8792 KB Output is correct
13 Correct 3 ms 8792 KB Output is correct
14 Correct 2 ms 8792 KB Output is correct
15 Correct 3 ms 8792 KB Output is correct
16 Correct 3 ms 8792 KB Output is correct
17 Correct 4 ms 8916 KB Output is correct
18 Correct 81 ms 8792 KB Output is correct
19 Correct 152 ms 8944 KB Output is correct
20 Correct 2 ms 8792 KB Output is correct
21 Correct 530 ms 8876 KB Output is correct
22 Correct 2 ms 8792 KB Output is correct
23 Correct 3 ms 8792 KB Output is correct
24 Correct 3 ms 8792 KB Output is correct
25 Correct 48 ms 8792 KB Output is correct
26 Correct 139 ms 8792 KB Output is correct
27 Correct 53 ms 8792 KB Output is correct
28 Correct 170 ms 8792 KB Output is correct
29 Correct 3 ms 8792 KB Output is correct
30 Correct 3 ms 8804 KB Output is correct
31 Correct 2 ms 8792 KB Output is correct
32 Correct 5 ms 8792 KB Output is correct
33 Correct 6 ms 8792 KB Output is correct
34 Correct 13 ms 8888 KB Output is correct
35 Incorrect 2 ms 8792 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 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 19 ms 8880 KB Output is correct
4 Correct 3 ms 8792 KB Output is correct
5 Correct 3 ms 8792 KB Output is correct
6 Correct 3 ms 8792 KB Output is correct
7 Correct 3 ms 8792 KB Output is correct
8 Correct 3 ms 8792 KB Output is correct
9 Correct 2 ms 8792 KB Output is correct
10 Correct 2 ms 8792 KB Output is correct
11 Correct 3 ms 8892 KB Output is correct
12 Correct 2 ms 8792 KB Output is correct
13 Correct 3 ms 8792 KB Output is correct
14 Correct 2 ms 8792 KB Output is correct
15 Correct 3 ms 8792 KB Output is correct
16 Correct 3 ms 8792 KB Output is correct
17 Correct 4 ms 8916 KB Output is correct
18 Correct 81 ms 8792 KB Output is correct
19 Correct 152 ms 8944 KB Output is correct
20 Correct 2 ms 8792 KB Output is correct
21 Correct 530 ms 8876 KB Output is correct
22 Correct 2 ms 8792 KB Output is correct
23 Correct 3 ms 8792 KB Output is correct
24 Correct 3 ms 8792 KB Output is correct
25 Correct 48 ms 8792 KB Output is correct
26 Correct 139 ms 8792 KB Output is correct
27 Correct 53 ms 8792 KB Output is correct
28 Correct 170 ms 8792 KB Output is correct
29 Correct 3 ms 8792 KB Output is correct
30 Correct 3 ms 8804 KB Output is correct
31 Correct 2 ms 8792 KB Output is correct
32 Correct 5 ms 8792 KB Output is correct
33 Correct 6 ms 8792 KB Output is correct
34 Correct 13 ms 8888 KB Output is correct
35 Incorrect 2 ms 8792 KB 1st lines differ - on the 1st token, expected: '235989424', found: '0'
36 Halted 0 ms 0 KB -