結果

問題 No.602 隠されていたゲーム2
ユーザー Nekosyndrome
提出日時 2017-12-02 06:29:52
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 81 ms / 2,000 ms
コード長 2,676 bytes
コンパイル時間 1,784 ms
コンパイル使用メモリ 166,508 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-12-16 00:02:37
合計ジャッジ時間 3,078 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 21
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
#define REP(x,y,z) for(int x=y;x<=z;x++)
#define FORD(x,y,z) for(int x=y;x>=z;x--)
#define MSET(x,y) memset(x,y,sizeof(x))
#define FOR(x,y) for(__typeof(y.begin()) x=y.begin();x!=y.end();x++)
#define F first
#define S second
#define MP make_pair
#define PB push_back
#define SZ size()
#define M 100005
void RI(){}
template<typename... T>
void RI( int& head, T&... tail ) {
    scanf("%d",&head);
    RI(tail...);
}
using namespace std;
typedef long long LL;
int n;
LL d[M],xt,yt;
vector<LL> d2[2];
pair<LL,LL> dis(LL x,pair<LL,LL> y)
{
    assert(y.F<=y.S);
    if (x < y.F)
        return MP(y.F-x, y.S-x);
    if (x > y.S)
        return MP(x-y.S, x-y.F);
    return MP(
        0LL, 
        max(x-y.F, y.S-x)
    );
}
LL findBetween(LL x,LL y,int z) //[x,y]
{
    assert(0<=z && z<=1);
    assert(x<=y);
    int pos = lower_bound(d2[z].begin(), d2[z].end(), x) - d2[z].begin();
    if(pos<(int)d2[z].size() && d2[z][pos]<=y) return d2[z][pos];
    return -1;
}
int getans(LL dd)
{
    if(dd == max(abs(xt), abs(yt)))
        return 1;
    
    LL tmp, tmp2;
    pair<LL,LL> rng;
    int mod;
    
    // +-dd, ?
    mod = ((dd+yt)%2+2)%2;
    rng = dis(yt, MP(-dd, dd)); //dy
    if (rng.F%2 != mod) rng.F++;
    if (rng.S%2 != mod) { rng.S--; assert(0); }
    if (rng.F > rng.S) {
        assert(0);
        rng = MP(1LL<<62, (1LL<<62)*-1);
    }
    tmp2 = min(abs(xt-dd), abs(xt+dd));
    if (rng.S >= tmp2) {
        tmp = findBetween(max(rng.F,tmp2), rng.S, mod);
        if(tmp!=-1) return 2;
    }
    if (rng.F <= tmp2) {
        tmp = findBetween(tmp2, tmp2, tmp2%2);
        if(tmp!=-1) return 2;
    }
    tmp2 = max(abs(xt-dd), abs(xt+dd));
    if (rng.F <= tmp2) {
        tmp = findBetween(tmp2, tmp2, tmp2%2);
        if(tmp!=-1) return 2;
    }
    // ?, +-dd
    mod = ((dd+xt)%2+2)%2;
    rng = dis(xt, MP(-dd, dd));
    if (rng.F%2 != mod) rng.F++;
    if (rng.S%2 != mod) { rng.S--; assert(0); }
    if (rng.F > rng.S) {
        assert(0);
        rng = MP(1LL<<62, (1LL<<62)*-1);
    }
    
    tmp2 = min(abs(yt-dd), abs(yt+dd));
    if (rng.S >= tmp2) {
        tmp = findBetween(max(rng.F,tmp2), rng.S, mod);
        if(tmp!=-1) return 2;
    }
    if (rng.F <= tmp2) {
        tmp = findBetween(tmp2, tmp2, tmp2%2);
        if(tmp!=-1) return 2;
    }
    tmp2 = max(abs(yt-dd), abs(yt+dd));
    if (rng.F <= tmp2) {
        tmp = findBetween(tmp2, tmp2, tmp2%2);
        if(tmp!=-1) return 2;
    }
    return 3;
}
int main()
{
    while(~scanf("%d",&n))
    {
        d2[0].clear();
        d2[1].clear();
        REP(i,1,n) {
            cin >> d[i];
            d2[d[i]%2].PB(d[i]);
        }
        sort(d+1, d+n+1);
        sort(d2[0].begin(), d2[0].end());
        sort(d2[1].begin(), d2[1].end());
        cin >> xt >> yt;
        {
            LL x2 = xt;
            xt += yt;
            yt = x2 - yt;
        }
        if(xt==0 && yt==0) {
            puts("0");
            continue;
        }
        int ans=3;
        REP(i,1,n) ans = min(ans, getans(d[i]));
        if(ans==3) ans=-1;
        printf("%d\n", ans);
    }
    return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0