Submission #825735

#	Time	Username	Problem	Language	Result	Execution time	Memory
825735		Amylopectin	Digital Circuit (IOI22_circuit)	C++17	18 / 100	3092 ms	98112 KiB

circuit

#include "circuit.h"
#include <stdio.h>
#include <vector>
using namespace std;
const long long mxn = 2e6 + 10,mo = 1000002022;
vector<long long> pat[mxn] = {},fa[mxn] = {};
long long n,m,dp[mxn][2] = {};
long long re(long long cn)
{
  long long i,j,k,fn,cva;
  if(cn >= n)
  {
    return 0;
  }
  fa[cn].clear();
  fa[cn].push_back(1);
  for(i=1; i<=pat[cn].size(); i++)
  {
    fa[cn].push_back(0);
  }
  for(i=0; i<pat[cn].size(); i++)
  {
    fn = pat[cn][i];
    re(fn);
    for(j=pat[cn].size(); j>=0; j--)
    {
      cva = 0;
      for(k=0; k<2; k++)
      {
        if(j-k < 0)
        {
          break;
        }
        cva += dp[fn][k] * fa[cn][j-k];
        cva %= mo;
      }
      fa[cn][j] = cva;
    }
  }
  dp[cn][0] = 0;
  dp[cn][1] = 0;
  for(i=0; i<=pat[cn].size(); i++)
  {
    dp[cn][0] += fa[cn][i] * (pat[cn].size() - i);
    dp[cn][1] += fa[cn][i] * i;
    dp[cn][0] %= mo;
    dp[cn][1] %= mo;
  }
  return 0;
}
void init(int N, int M, std::vector<int> pp, std::vector<int> aa) 
{
  long long i,j,cn,cm,fn,fm;
  n = N;
  m = M;
  for(i=0; i<n+m; i++)
  {
    pat[pp[i]].push_back(i);
  }
  for(i=0; i<m; i++)
  {
    if(aa[i] == 0)
    {
      dp[n+i][0] = 1;
    }
    else 
    {
      dp[n+i][1] = 1;
    }
    
  }

  return ;
}

int count_ways(int l, int r) 
{
  long long i,j,cn,cm,fn,fm;
  int ret;
  for(i=l; i<=r; i++)
  {
    if(dp[i][1] == 0)
    {
      dp[i][0] = 0;
      dp[i][1] = 1;
    }
    else 
    {
      dp[i][0] = 1;
      dp[i][1] = 0;
    }
  }
  re(0);
  ret = dp[0][1];
  return ret;
}

Compilation message (stderr)

circuit.cpp: In function 'long long int re(long long int)':
circuit.cpp:17:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |   for(i=1; i<=pat[cn].size(); i++)
      |            ~^~~~~~~~~~~~~~~~
circuit.cpp:21:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |   for(i=0; i<pat[cn].size(); i++)
      |            ~^~~~~~~~~~~~~~~
circuit.cpp:42:13: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |   for(i=0; i<=pat[cn].size(); i++)
      |            ~^~~~~~~~~~~~~~~~
circuit.cpp: In function 'void init(int, int, std::vector<int>, std::vector<int>)':
circuit.cpp:53:15: warning: unused variable 'j' [-Wunused-variable]
   53 |   long long i,j,cn,cm,fn,fm;
      |               ^
circuit.cpp:53:17: warning: unused variable 'cn' [-Wunused-variable]
   53 |   long long i,j,cn,cm,fn,fm;
      |                 ^~
circuit.cpp:53:20: warning: unused variable 'cm' [-Wunused-variable]
   53 |   long long i,j,cn,cm,fn,fm;
      |                    ^~
circuit.cpp:53:23: warning: unused variable 'fn' [-Wunused-variable]
   53 |   long long i,j,cn,cm,fn,fm;
      |                       ^~
circuit.cpp:53:26: warning: unused variable 'fm' [-Wunused-variable]
   53 |   long long i,j,cn,cm,fn,fm;
      |                          ^~
circuit.cpp: In function 'int count_ways(int, int)':
circuit.cpp:78:15: warning: unused variable 'j' [-Wunused-variable]
   78 |   long long i,j,cn,cm,fn,fm;
      |               ^
circuit.cpp:78:17: warning: unused variable 'cn' [-Wunused-variable]
   78 |   long long i,j,cn,cm,fn,fm;
      |                 ^~
circuit.cpp:78:20: warning: unused variable 'cm' [-Wunused-variable]
   78 |   long long i,j,cn,cm,fn,fm;
      |                    ^~
circuit.cpp:78:23: warning: unused variable 'fn' [-Wunused-variable]
   78 |   long long i,j,cn,cm,fn,fm;
      |                       ^~
circuit.cpp:78:26: warning: unused variable 'fm' [-Wunused-variable]
   78 |   long long i,j,cn,cm,fn,fm;
      |                          ^~

• Subtask 1: 2 / 2
• Subtask 2: 7 / 7
• Subtask 3: 9 / 9
• Subtask 4: 0 / 4
• Subtask 5: 0 / 12
• Subtask 6: 0 / 27
• Subtask 7: 0 / 28
• Subtask 8: 0 / 11