oj.uz

Submission #15495

# Submission time Handle Problem Language Result Execution time Memory
15495 2015-07-12T08:29:55 Z gs13068 쿼터너리 컴퓨터 (kriii3_Z) C++
126 / 126
 807 ms 1092 KB 
#include<cstdio>

int a[22],n,m;

int d[22];
int t[22];
int r[22];

int chk[22];
int eff[22][22];

int w[444];
int x[444];
int y[444];
int z[444];

void dfs(int p)
{
    if(p==n)
    {
        int i;
        for(i=0;i<n;i++)t[i]=d[i];
        for(i=0;i<m;i++)
        {
            if(w[i]==0)t[x[i]]=(t[y[i]]+t[z[i]])%4;
            if(w[i]==1)t[x[i]]=t[y[i]]^t[z[i]];
            if(w[i]==2)t[x[i]]=(t[y[i]]+z[i])%4;
            if(w[i]==3)t[x[i]]=t[y[i]]^z[i];
        }
        for(i=0;i<n;i++)r[i]=(r[i]+t[i])%4;
        return;
    }
    for(d[p]=0;d[p]<4;d[p]++)if(d[p]!=a[p])dfs(p+1);
}

void dfs2(int p,int q)
{
    if(p==n)
    {
        int i,j,k;
        for(i=0;i<n;i++)for(j=0;j<n;j++)eff[i][j]=0;
        for(i=0;i<n;i++)
        {
            t[i]=d[i];
            eff[i][i]=1;
        }
        for(i=0;i<m;i++)
        {
            if(w[i]==0)
            {
                t[x[i]]=(t[y[i]]+t[z[i]])%4;
                for(j=0;j<n;j++)eff[x[i]][j]=eff[y[i]][j]^eff[z[i]][j];
            }
            if(w[i]==1)
            {
                t[x[i]]=t[y[i]]^t[z[i]];
                for(j=0;j<n;j++)eff[x[i]][j]=eff[y[i]][j]^eff[z[i]][j];
            }
            if(w[i]==2)
            {
                t[x[i]]=(t[y[i]]+z[i])%4;
                for(j=0;j<n;j++)eff[x[i]][j]=eff[y[i]][j];
            }
            if(w[i]==3)
            {
                t[x[i]]=t[y[i]]^z[i];
                for(j=0;j<n;j++)eff[x[i]][j]=eff[y[i]][j];
            }
        }
        for(i=0;i<n;i++)
        {
            r[i]=(r[i]+t[i]*q)%4;
            for(j=0;j<n;j++)if(eff[i][j]&&d[j]!=a[j]&&(d[j]^2)!=a[j])break;
            if(j<n)r[i]=(r[i]+q)%4;
        }
        return;
    }
    for(d[p]=0;d[p]<2;d[p]++)
    {
        if(d[p]==a[p])d[p]^=2;
        dfs2(p+1,q*((d[p]!=a[p])+((d[p]^2)!=a[p])));
        if(d[p]>=2)d[p]^=2;
    }
}

int main()
{
    int i;
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++)scanf("%d",&a[i]);
    for(i=0;i<m;i++)scanf("%d%d%d%d",&w[i],&x[i],&y[i],&z[i]);
    dfs2(0,1);
    for(i=0;i<n;i++)printf("%d ",r[i]);
}

Subtask #1
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1092 KB Output is correct
2 Correct 0 ms 1092 KB Output is correct
3 Correct 0 ms 1092 KB Output is correct
4 Correct 0 ms 1092 KB Output is correct
5 Correct 0 ms 1092 KB Output is correct
6 Correct 0 ms 1092 KB Output is correct
7 Correct 0 ms 1092 KB Output is correct
8 Correct 0 ms 1092 KB Output is correct
9 Correct 0 ms 1092 KB Output is correct
10 Correct 0 ms 1092 KB Output is correct
11 Correct 0 ms 1092 KB Output is correct
12 Correct 0 ms 1092 KB Output is correct
13 Correct 1 ms 1092 KB Output is correct
14 Correct 0 ms 1092 KB Output is correct
15 Correct 8 ms 1092 KB Output is correct
16 Correct 8 ms 1092 KB Output is correct
17 Correct 36 ms 1092 KB Output is correct
18 Correct 33 ms 1092 KB Output is correct
19 Correct 38 ms 1092 KB Output is correct
20 Correct 40 ms 1092 KB Output is correct

Subtask #2
95.0 / 95.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 1092 KB Output is correct
2 Correct 181 ms 1092 KB Output is correct
3 Correct 385 ms 1092 KB Output is correct
4 Correct 807 ms 1092 KB Output is correct
5 Correct 81 ms 1092 KB Output is correct
6 Correct 170 ms 1092 KB Output is correct
7 Correct 362 ms 1092 KB Output is correct
8 Correct 772 ms 1092 KB Output is correct
9 Correct 72 ms 1092 KB Output is correct
10 Correct 153 ms 1092 KB Output is correct
11 Correct 321 ms 1092 KB Output is correct
12 Correct 669 ms 1092 KB Output is correct
13 Correct 78 ms 1092 KB Output is correct
14 Correct 176 ms 1092 KB Output is correct
15 Correct 369 ms 1092 KB Output is correct
16 Correct 777 ms 1092 KB Output is correct
17 Correct 73 ms 1092 KB Output is correct
18 Correct 165 ms 1092 KB Output is correct
19 Correct 362 ms 1092 KB Output is correct
20 Correct 737 ms 1092 KB Output is correct