Submission #6667380


Source Code Expand

Copy
#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

Submission Time
Task E - Golf
User bobuhiro11
Language C++14 (GCC 5.4.1)
Score 500
Code Size 3121 Byte
Status
Exec Time 325 ms
Memory 9452 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt
Subtask1 500 / 500 sample_01.txt, sample_02.txt, sample_03.txt, sub1_01.txt, sub1_02.txt, sub1_03.txt, sub1_04.txt, sub1_05.txt, sub1_06.txt, sub1_07.txt, sub1_08.txt, sub1_09.txt, sub1_10.txt, sub1_11.txt, sub1_12.txt, sub1_13.txt, sub1_14.txt, sub1_15.txt, sub1_16.txt, sub1_17.txt, sub1_18.txt, sub1_19.txt, sub1_20.txt, sub1_21.txt, sub1_22.txt, sub1_23.txt, sub1_24.txt, sub1_25.txt, sub1_26.txt, sub1_27.txt, sub1_28.txt, sub1_29.txt, sub1_30.txt, sub1_31.txt, sub1_32.txt, sub1_33.txt, sub1_34.txt, sub1_35.txt, sub1_36.txt, sub1_37.txt, sub1_38.txt, sub1_39.txt, sub1_40.txt, sub1_41.txt, sub1_42.txt, sub1_43.txt, sub1_44.txt, sub1_45.txt, sub1_46.txt, sub1_47.txt, sub1_48.txt, sub1_49.txt, sub1_50.txt, sub1_51.txt, sub1_52.txt
Case Name Status Exec Time Memory
sample_01.txt 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB
sub1_01.txt 1 ms 256 KB
sub1_02.txt 1 ms 256 KB
sub1_03.txt 1 ms 256 KB
sub1_04.txt 1 ms 256 KB
sub1_05.txt 1 ms 256 KB
sub1_06.txt 1 ms 256 KB
sub1_07.txt 1 ms 256 KB
sub1_08.txt 1 ms 256 KB
sub1_09.txt 1 ms 256 KB
sub1_10.txt 1 ms 256 KB
sub1_11.txt 1 ms 256 KB
sub1_12.txt 1 ms 256 KB
sub1_13.txt 1 ms 256 KB
sub1_14.txt 1 ms 256 KB
sub1_15.txt 1 ms 256 KB
sub1_16.txt 4 ms 384 KB
sub1_17.txt 1 ms 256 KB
sub1_18.txt 1 ms 256 KB
sub1_19.txt 1 ms 256 KB
sub1_20.txt 15 ms 764 KB
sub1_21.txt 1 ms 256 KB
sub1_22.txt 1 ms 256 KB
sub1_23.txt 1 ms 256 KB
sub1_24.txt 4 ms 256 KB
sub1_25.txt 1 ms 256 KB
sub1_26.txt 1 ms 256 KB
sub1_27.txt 1 ms 256 KB
sub1_28.txt 7 ms 384 KB
sub1_29.txt 1 ms 256 KB
sub1_30.txt 1 ms 256 KB
sub1_31.txt 1 ms 256 KB
sub1_32.txt 1 ms 256 KB
sub1_33.txt 7 ms 384 KB
sub1_34.txt 325 ms 9452 KB
sub1_35.txt 1 ms 256 KB
sub1_36.txt 1 ms 256 KB
sub1_37.txt 1 ms 256 KB
sub1_38.txt 1 ms 256 KB
sub1_39.txt 6 ms 384 KB
sub1_40.txt 1 ms 256 KB
sub1_41.txt 1 ms 256 KB
sub1_42.txt 1 ms 256 KB
sub1_43.txt 1 ms 256 KB
sub1_44.txt 1 ms 256 KB
sub1_45.txt 1 ms 256 KB
sub1_46.txt 3 ms 256 KB
sub1_47.txt 110 ms 3184 KB
sub1_48.txt 1 ms 256 KB
sub1_49.txt 1 ms 256 KB
sub1_50.txt 1 ms 256 KB
sub1_51.txt 112 ms 3184 KB
sub1_52.txt 1 ms 256 KB