AtCoder Grand Contest 016

Submission #1574103

Source codeソースコード

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define mp make_pair
#define f first
#define s second

int pos[100001];
int ed[100001];
int ed1[100001];
int r[100001];
ll a[100001];
ll b[100001];


int main(){
int i,j;
int n;
cin>>n;


pair<ll,int> c[n+1];
pair<ll,int> d[n+1];

ll xo=0;
int dis=0;
int in=0;
int o=0;
for(i=1;i<=n;i++)
    cin>>a[i];
for(i=1;i<=n;i++)
    cin>>b[i];
for(i=1;i<=n;i++)
{



    xo=xo^a[i];

    if(a[i]==b[i]){
        pos[i]=1;
        o++;

    }
    c[i].f=a[i];
    c[i].s=i;
    d[i].f=b[i];
    d[i].s=i;


}
sort(c+1,c+n+1);
sort(d+1,d+n+1);
int in2=1;
int yy=0;
for(i=1;i<=n;i++){

    if(in2>n)
        break;
    if(c[i].f==d[in2].f){
 int g,h;
 g=c[i].s;
 h=d[in2].s;
 if(pos[g]||pos[h]){
    if(pos[g])

    if(pos[h])
        {in2++;
        if(pos[g]==0)
        i--;}
    continue;

 }
  yy++;
  in2++;
  ed[g]=h;
  ed1[h]=g;


    }
    else{

         if(d[in2].f>c[i].f)
         continue;
    else
    {
        in2++;
        i--;

    }



    }



}


dis=o+yy;
dis=n-dis;
int in1=0;
for(i=1;i<=n;i++){

    if(pos[i])
        continue;
    if(ed1[i]==0)
        in=i;
        if(ed[i]==0)
            in1=i;

}



if(dis>=2||((dis==1)&&(xo!=b[in]))){
    cout<<-1<<endl;
    return 0;
}

int ans=0;
ed[in1]=in;

for(i=1;i<=n;i++){
    if(pos[i]==1)
        continue;
    if(r[i]==0){
        int fl=1;
        int ss=0;
        while(r[i]==0){


            r[i]=1;
            if(i==in1)
                fl=0;
            if(a[i]==xo)
                fl=0;
            i=ed[i];
            ss++;

        }


        ans=ans+fl+ss;

    }




}



cout<<ans<<endl;




return 0;
}

Submission

Task問題 D - XOR Replace
User nameユーザ名 adam1007
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 WA
Score得点 0
Source lengthソースコード長 1844 Byte
File nameファイル名
Exec time実行時間 ms
Memory usageメモリ使用量 -

Test case

Set

Set name Score得点 / Max score Cases
Sample - 0_00.txt,0_01.txt,0_02.txt,0_03.txt
All 0 / 1000 0_00.txt,0_01.txt,0_02.txt,0_03.txt,1_00.txt,1_01.txt,1_02.txt,1_03.txt,1_04.txt,1_05.txt,1_06.txt,1_07.txt,1_08.txt,1_09.txt,1_10.txt,1_11.txt,1_12.txt,1_13.txt,1_14.txt,1_15.txt,1_16.txt,1_17.txt,1_18.txt,1_19.txt,1_20.txt,1_21.txt,1_22.txt,1_23.txt,1_24.txt,1_25.txt,1_26.txt,1_27.txt,1_28.txt,1_29.txt,1_30.txt,1_31.txt,1_32.txt,1_33.txt,1_34.txt,1_35.txt,1_36.txt,1_37.txt,1_38.txt,1_39.txt,1_40.txt,1_41.txt,1_42.txt,1_43.txt,1_44.txt,1_45.txt,1_46.txt,1_47.txt,1_48.txt,1_49.txt,1_50.txt,1_51.txt,1_52.txt,1_53.txt,1_54.txt,1_55.txt,1_56.txt,1_57.txt,1_58.txt,1_59.txt,1_60.txt,1_61.txt,1_62.txt,1_63.txt,1_64.txt,1_65.txt,1_66.txt,1_67.txt,1_68.txt,1_69.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
0_00.txt AC 1 ms 256 KB
0_01.txt AC 1 ms 256 KB
0_02.txt AC 1 ms 256 KB
0_03.txt AC 1 ms 256 KB
1_00.txt AC 1 ms 256 KB
1_01.txt AC 1 ms 256 KB
1_02.txt AC 1 ms 256 KB
1_03.txt AC 1 ms 256 KB
1_04.txt AC 1 ms 256 KB
1_05.txt AC 1 ms 256 KB
1_06.txt AC 1 ms 256 KB
1_07.txt AC 62 ms 5376 KB
1_08.txt AC 69 ms 6144 KB
1_09.txt AC 62 ms 6144 KB
1_10.txt WA
1_11.txt AC 71 ms 5888 KB
1_12.txt WA
1_13.txt WA
1_14.txt WA
1_15.txt AC 91 ms 5888 KB
1_16.txt WA
1_17.txt AC 92 ms 5888 KB
1_18.txt WA
1_19.txt AC 97 ms 5888 KB
1_20.txt WA
1_21.txt AC 97 ms 5888 KB
1_22.txt WA
1_23.txt AC 98 ms 6016 KB
1_24.txt WA
1_25.txt AC 99 ms 6144 KB
1_26.txt WA
1_27.txt AC 98 ms 6016 KB
1_28.txt WA
1_29.txt AC 98 ms 6016 KB
1_30.txt WA
1_31.txt AC 97 ms 5760 KB
1_32.txt WA
1_33.txt AC 98 ms 5888 KB
1_34.txt WA
1_35.txt AC 98 ms 5760 KB
1_36.txt WA
1_37.txt AC 100 ms 5632 KB
1_38.txt WA
1_39.txt AC 97 ms 5760 KB
1_40.txt WA
1_41.txt AC 97 ms 5760 KB
1_42.txt WA
1_43.txt AC 96 ms 5760 KB
1_44.txt WA
1_45.txt AC 96 ms 5760 KB
1_46.txt WA
1_47.txt AC 94 ms 5632 KB
1_48.txt WA
1_49.txt AC 95 ms 5632 KB
1_50.txt WA
1_51.txt AC 91 ms 5504 KB
1_52.txt WA
1_53.txt AC 95 ms 5632 KB
1_54.txt WA
1_55.txt AC 92 ms 5504 KB
1_56.txt WA
1_57.txt AC 95 ms 5760 KB
1_58.txt WA
1_59.txt AC 95 ms 5760 KB
1_60.txt WA
1_61.txt AC 95 ms 5632 KB
1_62.txt WA
1_63.txt AC 91 ms 5504 KB
1_64.txt WA
1_65.txt AC 94 ms 5632 KB
1_66.txt WA
1_67.txt AC 94 ms 5632 KB
1_68.txt AC 97 ms 6144 KB
1_69.txt AC 95 ms 5760 KB