This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.
$left[i]$は$i$より背の高い人の数である．これを満たす列を返す．小さい順に埋めていくと場所が一意に定まる．左から何番目($0-indexed$)の空いている場所に埋めるか，と考えた．
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair
using namespace std ;
typedef long long ll ;
typedef pair < int , int > P ;
class StandInLine {
public :
vector < int > reconstruct ( vector < int > left ) {
int n = left . size ();
vector < int > ans ( n , - 1 );
rep ( i , n ) {
int j = 0 , cnt = 0 ;
while ( cnt != left [ i ]) {
if ( ans [ j ] == - 1 ) {
j ++ ;
cnt ++ ;
} else {
j ++ ;
}
}
while ( ans [ j ] != - 1 ) {
j ++ ;
}
ans [ j ] = i + 1 ;
}
return ans ;
}
};