求助,RE 90pts
  • 板块P1852 跳跳棋
  • 楼主Mihari
  • 当前回复2
  • 已保存回复2
  • 发布时间2021/7/23 17:31
  • 上次更新2023/11/4 13:32:57
查看原帖
求助,RE 90pts
125355
Mihari楼主2021/7/23 17:31

LOJ\rm LOJ 上可以过,这是测试信息

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

#define NDEBUG
#include<cassert>

namespace Elaina{
    #define rep(i, l, r) for(int i=(l), i##_end_=(r); i<=i##_end_; ++i)
    #define drep(i, l, r) for(int i=(l), i##_end_=(r); i>=i##_end_; --i)
    #define fi first
    #define se second
    #define mp(a, b) make_pair(a, b)
    #define Endl putchar('\n')
    #define mmset(a, b) memset(a, b, sizeof a)
    // #define int long long
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int, int> pii;
    typedef pair<ll, ll> pll;
    template<class T>inline T fab(T x){ return x<0? -x: x; }
    template<class T>inline void getmin(T& x, const T rhs){ x=min(x, rhs); }
    template<class T>inline void getmax(T& x, const T rhs){ x=max(x, rhs); }
    template<class T>inline T readin(T x){
        x=0; int f=0; char c;
        while((c=getchar())<'0' || '9'<c) if(c=='-') f=1;
        for(x=(c^48); '0'<=(c=getchar()) && c<='9'; x=(x<<1)+(x<<3)+(c^48));
        return f? -x: x;
    }
    template<class T>inline void writc(T x, char s='\n'){
        static int fwri_sta[1005], fwri_ed=0;
        if(x<0) putchar('-'), x=-x;
        do fwri_sta[++fwri_ed]=x%10, x/=10; while(x);
        while(putchar(fwri_sta[fwri_ed--]^48), fwri_ed);
        putchar(s);
    }
}
using namespace Elaina;

struct triple{
    int x, y, z;
    inline bool operator ==(const triple rhs) const{
        return x==rhs.x && y==rhs.y && z==rhs.z;
    }
    inline bool operator !=(const triple rhs) const{
        return !((*this)==rhs);
    }
    inline void print(){
        printf("(%d, %d, %d)\n", x, y, z);
    }
    /** @warning must ensure that x<y<z*/
    inline triple restore(){
        if(y-x==z-y) return triple{x, y, z};
        if(y-x<z-y){
            int len=z-y;
            if(len%(y-x)==0) return triple{z-((y-x)<<1), z-(y-x), z};
            return triple{z-(len%(y-x))-(y-x), z-(len%(y-x)), z}.restore();
        }
        else{
            int len=y-x;
            if(len%(z-y)==0) return triple{x, x+(z-y), x+((z-y)<<1)};
            return triple{x, x+(len%(z-y)), x+(len%(z-y))+(z-y)}.restore();
        }
    }
    inline int calc(){
        if(y-x==z-y) return 0;
        if(y-x<z-y){
            int len=z-y, cnt=len/(y-x);
            if(len%(y-x)==0) return cnt-1;
            return cnt+triple{z-(len%(y-x))-(y-x), z-(len%(y-x)), z}.calc();
        }
        else{
            int len=y-x, cnt=len/(z-y);
            if(len%(z-y)==0) return cnt-1;
            return cnt+triple{x, x+(len%(z-y)), x+(len%(z-y))+(z-y)}.calc();
        }
    }
    inline triple climb(int res){
        if(!res) return (*this);
        if(y-x<z-y){
            int len=z-y, cnt=len/(y-x);
            if(cnt<res) return triple{z-(len%(y-x))-(y-x), z-(len%(y-x)), z}.climb(res-cnt);
            else return triple{x+res*(y-x), y+res*(y-x), z};
        }
        else{
            int len=y-x, cnt=len/(z-y);
            if(cnt<res) return triple{x, x+(len%(z-y)), x+(len%(z-y))+(z-y)}.climb(res-cnt);
            else return triple{x, y-res*(z-y), z-res*(z-y)};
        }
    }
};

int shit[5];
triple s, t;

inline void input(){
    rep(i, 1, 3) shit[i]=readin(1);
    sort(shit+1, shit+4);
    s=triple{shit[1], shit[2], shit[3]};
    rep(i, 1, 3) shit[i]=readin(1);
    sort(shit+1, shit+4);
    t=triple{shit[1], shit[2], shit[3]};
}

signed main(){
    input();
    if(s.restore()!=t.restore())
        return printf("NO\n"), 0;
    else printf("YES\n");
    if(s==t) return printf("0\n"), 0;
    if(s.calc()<t.calc()) swap(s, t);
    int dep1=s.calc(), dep2=t.calc(), delta=dep1-dep2;
    s=s.climb(delta);
    if(s==t) return printf("%d\n", delta);
    else{
        int step=delta; dep1=dep2;
        for(int i=30; i>=0; --i) if(dep1>=(1<<i) && s.climb(1<<i)!=t.climb(1<<i)){
            step+=(1<<i)*2, s=s.climb(1<<i), t=t.climb(1<<i), dep1-=(1<<i);
        }
        writc(step+2);
    }
    return 0;
}
2021/7/23 17:31
加载中...