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.
問題文が全然読めなかった．数列$frontSlides$が与えられて，$frontSlides[i]$または$length - frontSlides[i]$として使える．場所を入れ替えたりせずに，このどちらを選ぶかによって辞書順にしたい．複数可能性があれば$MUPTIPLE\ SOLUTIONS$，唯一解があればそれを空白区切りで区切って，解がない場合は$NO\ SOLUTION$を返す．
まずはpairのfirstをそのまま，secondを$length$から引いたものとする．次に全ての要素に対して小さい方をfirstとする．次に辞書順になるように調整していく．$i$番目と$i+1$番目を比較する．first同士で$i+1$の方が大きければ何も変更なしに次を見る．そうでない場合は，$i+1$番目のsecondが$i$番目のfirstよりも大きければ，まだ辞書順を保てる．これもダメだった場合は$NO\ SOLUTION$．
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#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 RoadsAndFools {
public :
string determineOrientation ( int length , vector < int > frontSides ) {
int n = frontSides . size ();
vector < P > v ( n );
rep ( i , n ) {
v [ i ]. first = frontSides [ i ];
v [ i ]. second = length - frontSides [ i ];
}
rep ( i , n ) {
if ( v [ i ]. first > v [ i ]. second ) swap ( v [ i ]. first , v [ i ]. second );
}
bool flag = true ;
rep ( i , n - 1 ) {
if ( v [ i ]. first < v [ i + 1 ]. first ) continue ;
else if ( v [ i ]. first >= v [ i + 1 ]. first && v [ i ]. first < v [ i + 1 ]. second ) {
swap ( v [ i + 1 ]. first , v [ i + 1 ]. second );
}
else flag = false ;
}
if ( ! flag ) return "NO SOLUTION" ;
int cnt = 0 ;
rep ( i , n ) {
if ( v [ i ]. first == v [ i ]. second ) continue ;
swap ( v [ i ]. first , v [ i ]. second );
bool flag = true ;
rep ( j , n - 1 ) {
if ( v [ j ]. first < v [ j + 1 ]. first ) continue ;
flag = false ;
}
cnt += flag ;
swap ( v [ i ]. first , v [ i ]. second );
}
if ( cnt != 0 ) return "MULTIPLE SOLUTIONS" ;
stringstream ss ;
rep ( i , n ) {
if ( i ) ss << " " ;
ss << v [ i ]. first ;
}
return ss . str ();
}
};