Submission #6667380

---

Source Code Expand

#include <bits/stdc++.h>

#define rep(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

// 事前に、X>=0,Y>=0 にしておく
// 1. X+Yが奇数 かつ Kが偶数
//    -1, どうやっても奇数番地にはたどり着けない
// 2. X+Y>K
//    n=ceil(X+Y/K)として、X+Y と nK の偶奇が異れば n++
//    余剰 nK-X-Y のために、冗長な経路を作る。
// 
//      t = (nK-X-Y)/2
//
//            +
//            |
//            | Y
//      +     |
//    t |     | t 
//      |-----|
//         X
// 
// 3. X+Y<K
// 3-1. X+Yが偶数, n=2となる
//      t = (2K-X-Y)/2
//
//            +
//            |
//            | Y
//      +     |
//    t |     | t 
//      |-----|
//         X
// 
// 3-1. X+Yが奇数（1より、Kも奇数）
//      n=3になる
//      これが難しい
//
//      2(t+p) = 3K-(X+Y), t=K-X, p=(K+X-Y)/2
//      pとtが正、かつ p,t < K となるように
//                       p
//                     +----+
//                          |
//                          | Y
//               +          |
//             t |          | t
//               |----------|
//                 X     p
// 4. X+Y==Kは自明

ll K,X,Y;
ll sign_x = 1, sign_y = 1;
bool swp = false;

void print(vector<PLL> ans) {
  cout<<ans.size()<<endl;

  rep(i,0,ans.size()){
    if (swp)
      swap(ans[i].first, ans[i].second);
    ans[i].first  *= sign_x;
    ans[i].second *= sign_y;
  }
  if (swp)
    swap(X,Y);
  if (sign_x) X*=sign_x;
  if (sign_y) Y*=sign_y;

  rep(i,0,ans.size()) cout<<ans[i].first<< " " << ans[i].second<<endl;

  assert(ans[ans.size()-1].first == X);
  assert(ans[ans.size()-1].second == Y);
  rep(i,0,ans.size()) if (i > 0) assert(abs(ans[i].first-ans[i-1].first) + abs(ans[i].second-ans[i-1].second) == K);
}

signed main() {
  cin>>K>>X>>Y;

  if (X<0) { X*=-1; sign_x = -1;}
  if (Y<0) { Y*=-1; sign_y = -1;}
  if (X<Y){
    swap(X,Y);
    swp=true;
  }

  if ((X+Y)%2==1 && K%2==0) {
    cout<<-1<<endl;
    return 0;
  }

  if (X+Y == K) {
    vector<PLL> ans;
    ans.push_back(PLL(X,Y));
    print(ans);
    return 0;
  }

  if (X+Y < K && (X+Y)%2 == 1) {
    ll p=(K+X-Y)/2;
    vector<PLL> ans;
    ans.push_back(PLL(X, -(K-X)));
    ans.push_back(PLL(X+p, Y-(K-p)));
    ans.push_back(PLL(X, Y));
    print(ans);
    return 0;
  }

  // 移動回数の決定
  ll n;
  if (X+Y < K && (X+Y)%2 == 0) {
    n = 2;
  } else {
    //ll c = (K -(X+Y % K)) %K;
    //if (c%2==0) {
    //  n = (X+Y +K-1) / K;
    //} else {
    //  n = (X+Y +K-1) / K + 1;
    //}
    n = (X+Y +K-1) / K;
    if ( (n*K)%2 != (X+Y)%2 )
      n++;
  }

  ll t = (n*K-X-Y)/2;
  vector<PLL> ans;
  for (ll i=0; i<n; i++){
    ll d = (i+1)*K;
    if (d<=t) {
      ans.push_back(PLL(0, -d));
    } else if (d<=X+t) {
      ans.push_back(PLL(d-t, -t));
    } else {
      ans.push_back(PLL(X, -t+(d-X-t)));
    }
  }
  print(ans);
  return 0;
}

Submission Info

Judge Result