結果

問題 No.1355 AND OR GAME
コンテスト
ユーザー Drice
提出日時 2021-01-17 15:54:40
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 81 ms / 2,000 ms
コード長 1,556 bytes
コンパイル時間 247 ms
コンパイル使用メモリ 33,152 KB
実行使用メモリ 5,504 KB
最終ジャッジ日時 2024-11-29 19:02:45
合計ジャッジ時間 9,205 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 95
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
long long a[200005];
int p[200005];
long long bit[70];
long long have[70];
//0: must 0
//1: must 1
//2: ok

void factor(long long u,int n,long long bit[]){
    for(int i = 1; i <= n; i++){
        bit[i] = u%2;
        u /= 2;
    }
}

int main(){
    int n; long long x,y;
    scanf("%d%lld%lld",&n,&x,&y);
    a[1] = x;
    n++;
    for(int i = 2; i <= n; i++) scanf("%lld",&a[i]);
    int len = 60;
    factor(y,len,bit);
    int find = -1;
    for(int i = n; i >= 1; i--){
        int cnt0 = 0, cnt1 = 0;
        factor(a[i],len,have);
        for(int j = 1; j <= len; j++){
            if(bit[j]!=2 && bit[j]!=have[j]){
                if(have[j]) cnt1++;
                else cnt0++;
            }
        }
        if(!cnt0 && !cnt1){
            find = i;
            p[i] = 3;
            break;
        }
        else{
            if(cnt0 && cnt1) break;
            else if(cnt0){
                p[i] = 2;
                for(int j = 1; j <= len; j++){
                    if(have[j]){
                        if(bit[j]==1) bit[j] = 2;
                    }
                }
            }
            else{
                p[i] = 1;
                for(int j = 1; j <= len; j++){
                    if(!have[j]){
                        if(bit[j]==0) bit[j] = 2;
                    }
                }
            }
        }
    }
    if(find==-1) printf("-1\n");
    else{
        for(int i = 1; i < find; i++) p[i] = 2;
        for(int i = 2; i <= n; i++) printf("%d ",p[i]);
        printf("\n");
    }
    return 0;
}
0