Submission #632015

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
632015	2022-08-19T10:00:10 Z	TimDee	Digital Circuit (IOI22_circuit)	C++17	9 / 100	10 ms	2900 KB

circuit

#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;

int p1=0, n, m;
vector<int> p, a;
vector<vector<int>> in(1e3+3);

void _p1() {
  p1=1;
}

void init(int N, int M, vector<int> P, vector<int> A) {

  n=N, m=M, p=P, a=A;
  if (n==1) _p1();
  for (int i=1; i<n+m; ++i) {
    in[p[i]].push_back(i);
  }

}

int count_ways(int l, int r) {

  for (int i=l-n; i<=r-n; ++i) a[i]^=1;
  if (p1) {
    int s=0;
    for (int i=0; i<m; ++i) s+=a[i];
    return s;
  }

  vector<vector<ll>> dp(n,{0,0});

  for (int i=n-1; i>=0; --i) {
    int cnt=0;
    int inp=0;
    int f=-1;
    for (auto x:in[i]) {
      if (x>=n) cnt+=a[x-n];
      else f=x;
      inp+=x>=n;
    }
    if (inp==2) {
      dp[i]={2-cnt,cnt};
    } else if (inp==1) {
      if (cnt) {
        dp[i][1]=(dp[f][0]+dp[f][1]+dp[f][1])%1000002022;
        dp[i][0]=dp[f][0];
      } else {
        dp[i][1]=dp[f][1];
        dp[i][0]=(dp[f][1]+dp[f][0]+dp[f][0])%1000002022;
      }
    } else {
      int s=in[i][0];
      dp[i][1]=(1ll*dp[f][1]*(dp[s][0]+dp[s][1])+1ll*dp[s][1]*(dp[f][0])+1ll*dp[s][1]*dp[f][1])%1000002022;
      dp[i][0]=(1ll*dp[f][0]*dp[s][0]+1ll*dp[f][0]*dp[s][0]+1ll*dp[f][1]*dp[s][0]+1ll*dp[s][1]*dp[f][0])%1000002022;
    }
  }

  //for (auto x:dp) cout<<x[1]<<' '<<x[0]<<'\n';

  return dp[0][1];

}

Subtask #1
2.0 / 2.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	0 ms	208 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct

Subtask #2
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	1 ms	352 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	432 KB	Output is correct
8	Correct	2 ms	336 KB	Output is correct
9	Correct	1 ms	336 KB	Output is correct
10	Correct	1 ms	424 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct

Subtask #3
0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	0 ms	208 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct
9	Correct	1 ms	208 KB	Output is correct
10	Correct	1 ms	352 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Correct	1 ms	336 KB	Output is correct
15	Correct	1 ms	432 KB	Output is correct
16	Correct	2 ms	336 KB	Output is correct
17	Correct	1 ms	336 KB	Output is correct
18	Correct	1 ms	424 KB	Output is correct
19	Correct	1 ms	336 KB	Output is correct
20	Correct	1 ms	336 KB	Output is correct
21	Runtime error	1 ms	592 KB	Execution killed with signal 11
22	Halted	0 ms	0 KB	-

Subtask #4
0 / 4.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	10 ms	2900 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #5
0 / 12.0

#	Verdict	Execution time	Memory	Grader output
1	Runtime error	10 ms	2900 KB	Execution killed with signal 11
2	Halted	0 ms	0 KB	-

Subtask #6
0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	1 ms	352 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	432 KB	Output is correct
8	Correct	2 ms	336 KB	Output is correct
9	Correct	1 ms	336 KB	Output is correct
10	Correct	1 ms	424 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct
13	Runtime error	10 ms	2900 KB	Execution killed with signal 11
14	Halted	0 ms	0 KB	-

Subtask #7
0 / 28.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	0 ms	208 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct
9	Correct	1 ms	208 KB	Output is correct
10	Correct	1 ms	352 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Correct	1 ms	336 KB	Output is correct
15	Correct	1 ms	432 KB	Output is correct
16	Correct	2 ms	336 KB	Output is correct
17	Correct	1 ms	336 KB	Output is correct
18	Correct	1 ms	424 KB	Output is correct
19	Correct	1 ms	336 KB	Output is correct
20	Correct	1 ms	336 KB	Output is correct
21	Runtime error	1 ms	592 KB	Execution killed with signal 11
22	Halted	0 ms	0 KB	-

Subtask #8
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	0 ms	208 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	336 KB	Output is correct
6	Correct	1 ms	336 KB	Output is correct
7	Correct	1 ms	336 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct
9	Correct	1 ms	208 KB	Output is correct
10	Correct	1 ms	352 KB	Output is correct
11	Correct	1 ms	336 KB	Output is correct
12	Correct	1 ms	336 KB	Output is correct
13	Correct	1 ms	336 KB	Output is correct
14	Correct	1 ms	336 KB	Output is correct
15	Correct	1 ms	432 KB	Output is correct
16	Correct	2 ms	336 KB	Output is correct
17	Correct	1 ms	336 KB	Output is correct
18	Correct	1 ms	424 KB	Output is correct
19	Correct	1 ms	336 KB	Output is correct
20	Correct	1 ms	336 KB	Output is correct
21	Runtime error	1 ms	592 KB	Execution killed with signal 11
22	Halted	0 ms	0 KB	-

Submission #632015

Compilation message