(AGC002 C - Knot Puzzle)
ロープの結び目が全て切れないのは、どの隣同士の二つのロープを選んでも長さの和がL以上にならない時。
なぜなら、L以上になる隣同士のロープの組みが存在する時、その二本を中心として両端から結び目を解いていけば良い。(これを出力)
逆に、存在しないとき、どのような結び目の外し方をしても最後に二本残ったものの結び目を外すことができない。
300点くらいに感じるんだけど500点なのか…
でもこの前尊敬する某氏が「だいたい点数は体感難しさにあっている」とおっしゃっていたので、多分精進が足りなくて典型問題が解けなかったりしてるんだろうな
#include<cstdio> #include<math.h> #include<algorithm> #include<vector> #include<queue> #include<string> #include<set> #include<cstring> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) #define INF 1001001001 #define LLINF 1001001001001001001 #define mp make_pair #define pb push_back #define LLIandI pair<long long int , int> #define ll long long ll int N,L; ll int a[100003]; int main(){ scanf("%lld %lld",&N,&L); ll int maxa=0; ll int maxi=0; rep(i,N){ scanf("%lld",&a[i]); if(i>0&&a[i]+a[i-1]>maxa){ maxa=a[i]+a[i-1];maxi=i-1; } } if(maxa<L){ printf("Impossible\n"); return 0; } printf("Possible\n"); rep(i,N-1){ if(i<maxi)printf("%d\n",i+1); if(i>=maxi)printf("%d\n",N-1-i+maxi); } }