AGC 002 C - Knot Puzzle (500)

• 問題

問題概要

a[i] (1<=i<=N) の長さのロープN本がある.これらは順に繋がっている.
長さがLより小さくならないように一つずつ結び目を解くことができるか,できる時解き方を出力せよ.
2 <= N <= 10⁵, 1 <= a_i,L <= 10⁹

解法

解くことができる <-> a[i] + a[i+1] >= Lなるiが存在する
と言い換えることができる.
このようなiを発見したら,1,2,..,i-1, N,N-1,..,i
とすれば必ず解くことができる.

メモ

両端から短い方を解く,としたらWAした.
反例は
4 5
2 3 1 3 とか.
必要条件から考えていくべきだった.

コード

#include "bits/stdc++.h"

#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,0,n)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define pb push_back

using namespace std;

using ll = long long;
using P = pair<int,int>;

const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll LINF=1LL<<60, lmod = 1e9+7;

const int MAX_N = 100005;

ll a[MAX_N];

int main(){
  ll N,L; cin >> N >> L;
  ll re = 0LL; int r = 0;
  rep(i,N) scanf("%lld",a+i);
  rep(i,N-1){
    ll t = a[i] + a[i+1];
    if(t>re){
      re = t;
      r = i;
    }
  }
  if(re<L) cout << "Impossible" << endl;
  else{
    cout << "Possible" << endl;
    REP(i,1,r+1) cout << i << endl;
    RREP(i,N-1,r+1) cout << i << endl;
  }
  return 0;
}