글 읽기 - 다른 사이트에서는 맞는데 여기서는 틀려서 도움 부탁드립니다.

leehosu01 6년 전 0

http://www.jungol.co.kr/theme/...
여기서는 맞는데 백준 에서는 틀리네요(9%에서 틀리네요).

역시 백준은 데이터가 빡빡한것 같네요 지금까지 테스트케이스 1000개정도 해봤는데 다 맞게 나오던데 ,(6<=n<=15,k=2)

뭐가 문제일까요?

#include<bits/stdc++.h>
using namespace std;
#define grynum(A,B) (!(((A)^(B))&(((A)^(B))-1)))
int Hs,k,N,M,DS,go[2][2];
int lc[15],MODing;


int NGB(int num){return num ^ (num >> 1);}//GrayBuild
int RVGB(int num){int i,D=0,ER=NGB(num);
for(i=0;i!=M;i++)if(ER&(1<<i))D|=(1<<(M-i-1));
return D;

}//GrayBuild
int RGB(int num){int i,D=0,ER=NGB(num);
for(i=0;i!=M;i++)if(ER&(1<<i))D|=(1<<(lc[i]));
return D;

}//GrayBuild
void rnd()
{
    for(int i=min(M-1,6);i;i--)
        swap(lc[rand()%M],lc[rand()%M]);
}

int (*GB)( int);
void pgo(int A)
{
    for(int i=0;i<M;i++)
        printf("%d",(A&(1<<i))!=0);
}
void pin(){
    int i,I,j,STGO;
    for(j=0;j<1<<M;j++)
    if(!(GB(j)^Hs)){STGO=j;break;}
    for(j=STGO;j<1<<M;j++)
    {I=GB(j)^Hs;
        if(j!=STGO&&(j-STGO&7)==0)printf("\n");
        pgo(I);
        printf(" ");
    }
    for(j=0;j<STGO;j++)
    {I=GB(j)^Hs;
        if((j+(1<<M)-STGO&7)==0)printf("\n");
        pgo(I);
        printf(" ");
    }
}

int DPG[1<<15];
bool pro2(int H)
{
Hs=H;
    int F=DS-1,i;
    if(!k)return 1;
    if(GB((DPG[go[1][0]^H]+1)&F)==(go[1][1]^H))return 1;
    if(GB((DPG[go[1][0]^H]-1)&F)==(go[1][1]^H))return 1;
    return 0;
}
bool pro1()
{
    for(int i=0;i!=DS;i++)DPG[GB(i)]=i;

    int F=DS-1,i;

    for(i=1;i!=DS;i++)if((GB(i)^(GB(i-1)^go[0][0]))==go[0][1]){/*printf("call :: (0,0):: %d: %d (0,1):: %d: %d\n",i-1,GB(i-1),i,GB(i));*/if(pro2((GB(i-1)^go[0][0])))return 1;}
    if((GB(0)^(GB(F)^go[0][0]))==go[0][1]){/*printf("call :: (0,0):: %d: %d (0,1):: %d: %d\n",F,GB(F),0,GB(0));*/if(pro2((GB(F)^go[0][0])))return 1;}
    for(i=0;i!=F;i++)if((GB(i)^(GB(i+1)^go[0][0]))==go[0][1]){/*printf("call :: (0,0):: %d: %d (0,1):: %d: %d\n",i+1,GB(i+1),i,GB(i));*/if(pro2((GB(i+1)^go[0][0])))return 1;}
    if((GB(F)^(GB(0)^go[0][0]))==go[0][1]){/*printf("call :: (0,0):: %d: %d (0,1):: %d: %d\n",0,GB(0),F,GB(F));*/if(pro2((GB(0)^go[0][0])))return 1;}

    return 0;
}
bool pro()
{
    int t=11110;
    GB=NGB;if(pro1())return 1;
    MODing=1;GB=RVGB;if(pro1())return 1;
    for(int i=0;i<M;i++)lc[i]=i;
    GB=RGB;do{++MODing;rnd();if(pro1())return 1;}while(--t);
    return 0;
}
int SC01()
{
    string s;
    int ds=0;
    cin>>s;
    for(char&I:s)ds|=(I&1)<<(&I-&s[0]);
    return ds;
}
int main()
{
fill(DPG,DPG+(1<<15),0);
srand(1561651);
    cin>>M>>k;
    N=M-1;
    int i,j;DS=(1<<M);
    for(i=0;i<k*2;i++)
    {
        go[i/2][i&1]=SC01();
    }

    for(i=0;i<k;i++)if(!grynum(go[i][0],go[i][1])){printf("-1");return 0;}

    k--;
    if(!pro())printf("-1");
    else pin();
    return 0;
}

leehosu01 6년 전 0

추가로 제가 맞았다고 우기는게 아닙니다.

애초에 random 의 힘을 빌린거라 당연히 틀리기 쉽습니다.

그런데 혹시 도움을 받을수 있을까 싶어서 질문 올립니다.

그리고 오답을 일으키는 데이터를 알게되면 감사하겠습니다

#include<bits/stdc++.h>
using namespace std;
#define grynum(A,B) (!(((A)^(B))&(((A)^(B))-1)))
int Hs,k,N,M,DS,go[2][2];
int lc[15],MODing;


int NGB(int num){return num ^ (num >> 1);}//GrayBuild
int RVGB(int num){int i,D=0,ER=NGB(num);
for(i=0;i!=M;i++)if(ER&(1<<i))D|=(1<<(M-i-1));
return D;

}//GrayBuild
int RGB(int num){int i,D=0,ER=NGB(num);
for(i=0;i!=M;i++)if(ER&(1<<i))D|=(1<<(lc[i]));
return D;

}//GrayBuild
void rnd()
{
    for(int i=min(M-1,6);i;i--)
        swap(lc[rand()%M],lc[rand()%M]);
}

int (*GB)( int);
void pgo(int A)
{
    for(int i=0;i<M;i++)
        printf("%d",(A&(1<<i))!=0);
}
void pin(){
    int i,I,j,STGO;
    for(j=0;j<1<<M;j++)
    if(!(GB(j)^Hs)){STGO=j;break;}
    for(j=STGO;j<1<<M;j++)
    {I=GB(j)^Hs;
        if(j!=STGO&&(j-STGO&7)==0)printf("\n");
        pgo(I);
        printf(" ");
    }
    for(j=0;j<STGO;j++)
    {I=GB(j)^Hs;
        if((j+(1<<M)-STGO&7)==0)printf("\n");
        pgo(I);
        printf(" ");
    }
}

int DPG[1<<15];
bool pro2(int H)
{
Hs=H;
    int F=DS-1,i;
    if(!k)return 1;
    if(GB((DPG[go[1][0]^H]+1)&F)==(go[1][1]^H))return 1;
    if(GB((DPG[go[1][0]^H]-1)&F)==(go[1][1]^H))return 1;
    return 0;
}
bool pro1()
{
    for(int i=0;i!=DS;i++)DPG[GB(i)]=i;

    int F=DS-1,i;

    for(i=1;i!=DS;i++)if((GB(i)^(GB(i-1)^go[0][0]))==go[0][1]){/*printf("call :: (0,0):: %d: %d (0,1):: %d: %d\n",i-1,GB(i-1),i,GB(i));*/if(pro2((GB(i-1)^go[0][0])))return 1;}
    if((GB(0)^(GB(F)^go[0][0]))==go[0][1]){/*printf("call :: (0,0):: %d: %d (0,1):: %d: %d\n",F,GB(F),0,GB(0));*/if(pro2((GB(F)^go[0][0])))return 1;}
    for(i=0;i!=F;i++)if((GB(i)^(GB(i+1)^go[0][0]))==go[0][1]){/*printf("call :: (0,0):: %d: %d (0,1):: %d: %d\n",i+1,GB(i+1),i,GB(i));*/if(pro2((GB(i+1)^go[0][0])))return 1;}
    if((GB(F)^(GB(0)^go[0][0]))==go[0][1]){/*printf("call :: (0,0):: %d: %d (0,1):: %d: %d\n",0,GB(0),F,GB(F));*/if(pro2((GB(0)^go[0][0])))return 1;}

    return 0;
}
bool pro()
{
    int t=11110;
    GB=NGB;if(pro1())return 1;
    MODing=1;GB=RVGB;if(pro1())return 1;
    for(int i=0;i<M;i++)lc[i]=i;
    GB=RGB;do{++MODing;rnd();if(pro1())return 1;}while(--t);
    return 0;
}
int SC01()
{
    string s;
    int ds=0;
    cin>>s;
    for(char&I:s)ds|=(I&1)<<(&I-&s[0]);
    return ds;
}
int mainP()
{
srand(1561651);
fill(DPG,DPG+(1<<15),0);
    cin>>M>>k;
    N=M-1;
    int i,j;DS=(1<<M);
    for(i=0;i<k*2;i++)
    {
        go[i/2][i&1]=SC01();
    }

    for(i=0;i<k;i++)if(!grynum(go[i][0],go[i][1])){printf("-1");return 0;}

    k--;
    if(!pro())printf("-1");
    else pin();
    return 0;
}
void pout(int A,int ns){for(int j=0;j<ns;j++)printf("%d",(A&(1<<j))!=0);printf(" ");}
int main()
{

bool usPo[1<<15];
    FILE*fp;
    fp=fopen("ddo.txt","w");
    srand(1546);
    int i,j;
    for( i=0;i<6;i++)//이숫자를 키우면 TC를 늘림
    {

        fprintf(fp,"A");
        int ns,KK[2][2];
        freopen("in.txt","w",stdout);
        cout<<(ns=rand()%10+6)<<' '<<2<<'\n';
        pout(KK[0][0]=(rand()&((1<<ns)-1)),ns);
        pout(KK[0][1]=(KK[0][0]^(1<<(rand()%ns))),ns);
        pout(KK[1][0]=(rand()&((1<<ns)-1)),ns);
        pout(KK[1][1]=(KK[1][0]^(1<<(rand()%ns))),ns);
        /*pout(KK[1][0]=KK[0][0],ns);
        pout(KK[1][1]=KK[0][1],ns);*/
        fclose(stdout);
        fprintf(fp,"B");
        freopen("in.txt","r",stdin);
        freopen("out.txt","w",stdout);
        mainP();
        fclose(stdin);
        fclose(stdout);
        fprintf(fp,"C");
        freopen("out.txt","r",stdin);
        int d[3],f;
        d[0]=SC01();f=d[0];
        if(d[0]!=-1)
        {
            fill(usPo,usPo+(1<<15),0);
            usPo[d[0]]=1;
            d[1]=SC01();
            usPo[d[1]]=1;
            for(j=2;j<(1<<ns);j++)
            {d[j%3]=SC01();
                if(usPo[d[j%3]]){fprintf(fp,"by reused%d",j);break;}
                usPo[d[j%3]]=1;
                if(d[(j+2)%3]==KK[0][0])if(!(d[(j+1)%3]==KK[0][1]||d[(j)%3]==KK[0][1]))break;
                else if(d[(j+2)%3]==KK[1][0])if(!(d[(j+1)%3]==KK[1][1]||d[(j)%3]==KK[1][1]))break;
            }
            if(j==(1<<ns))
            {
                d[j%3]=f;
                if(d[(j+2)%3]==KK[0][0])if(!(d[(j+1)%3]==KK[0][1]||d[(j)%3]==KK[0][1]))j--;
                else if(d[(j+2)%3]==KK[1][0])if(!(d[(j+1)%3]==KK[1][1]||d[(j)%3]==KK[1][1]))j--;
                j++;
            }
            fprintf(fp,"%d::%s\n",i,((j==(1<<ns)+1)?"correct":"wrong"));
        }
        else fprintf(fp,"%d::%s\n",i,"-1??");
        fclose(stdin);
        fprintf(fp,"fin %d\n",i);
    }
        fclose(fp);

}

dngnogu 5년 전 0

@startlink 입력 데이터나 스페셜 저지에 문제가 있는지 확인해 주실 수 있으신가요?

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

다른 사이트에서는 맞는데 여기서는 틀려서 도움 부탁드립니다.

leehosu01 6년 전 0

leehosu01 6년 전 0

dngnogu 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말