本番サイトの不調としょうもないWAでグダグダだと思ったけど、終わってみるとそこそこの順位。
http://codeforces.com/contest/761/problem/D
問題
N要素の整数列A[i],B[i]からC[i]=B[i]-A[i]を作る。
A[i]は入力で与えられる。またC[i]は直接値が与えられるわけではないが、N要素中何番目に大きいかが与えられる。
L≦B[i]≦Rの範囲でB[i]を適切に設定したとき、Cが条件を満たすようにできるか。
できるならその一例を示せ。
解法
C[i]の小さい順に値を決めていこう。
今C[x]の値が確定し、次に大きなC[y]の値を決めるものとする。
C[y]≧C[x]+1より、B[y]-A[y]≧C[x]+1なのでB[y]≧C[x]+A[y]+1である。
今値を小さい順に決めていくので、あとはL≦B[y]≦Rのうち条件を満たす最小値を順次B[y]に当てはめていけばよい。
int N,L,R; int A[101010],B[101010]; pair<int,int> P[101010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>L>>R; FOR(i,N) cin>>A[i]; FOR(i,N) cin>>P[i].first, P[i].second=i; sort(P,P+N); int pre=-1LL<<30; FOR(i,N) { x=P[i].second; int need=pre+1+A[x]; if(need>R) return _P("-1\n"); need=max(L,need); B[x]=need; pre=B[x]-A[x]; } FOR(i,N) _P("%d%c",B[i],(i==N-1)?'\n':' '); }
まとめ
Div2とはいえ2000ptにしては簡単なような。