neerc I

gistfile1.cpp

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <bitset>
#include <queue>
#include <sstream>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define iter(v) __typeof((v).begin())
#define foreach(it, v) for (iter(v) it = (v).begin(); it != (v).end(); it++)
#define pb push_back
#define mp make_pair
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
ll sqr(ll x) {return x * x;}
template <class T> void checkmax(T &t, T x){if (x > t) t = x;}
template <class T> void checkmin(T &t, T x){if (x < t) t = x;}
template <class T> void _checkmax(T &t, T x){if (t == -1 || x > t) t = x;}
template <class T> void _checkmin(T &t, T x){if (t == -1 || x < t) t = x;}
ll power_mod(ll a, int b, int p) {
    ll ret = 1;
	for (; b; b >>= 1) {
		if (b & 1) ret = ret * a % p;
		a = a * a % p;
	}
	return ret;
}

template <class T>T ext_gcd(T a,T b,T& x,T& y){
	T t,ret;
	if (!b){
		x=1,y=0;
		return a;
	}
	ret=ext_gcd(b,a%b,x,y);
	t=x,x=y,y=t-a/b*y;
	return ret;
}

const int N = 100005;
const int M = 405;
int n, P, Q;
ll w[N];
int a[N], b[N];
int mat[M][M];
int f[M / 2][M][M];
int choose[M / 2][M][M];
bool s[N];

void rec(int i, int bestl, int bestr) {
    while (i) {
        int mask = choose[i][bestl][bestr];
        s[i] = mask & 1;
        s[n - i + 1] = mask & 2;
        bestl -= mask & 1;
        bestr -= !!(mask & 2);
        i--;
    }
}

void dp() {
    n = P + Q;
    memset(f, 0xff, sizeof(f));
    f[0][0][0] = 0;
    for (int i = 1; i * 2 <= n; i++) {
        rep (j, i) {
            rep (k, i) {
                if (f[i - 1][j][k] != -1) {
                    rep (mask, 4) {
                        int l = j + (mask & 1);
                        int r = k + (!!(mask & 2));
                        if (l + r > P) continue;
                        int tmp = f[i - 1][j][k];
                        tmp += mat[l][i];
                        if (!(i == n - i)) tmp += mat[P - l][n - i];
                        if (l != r) {
                            tmp += mat[r][i];
                            if (!(i == n - i)) tmp += mat[P - r][n - i];
                        }
                        if (tmp > f[i][l][r]) {
                            f[i][l][r] = tmp;
                            choose[i][l][r] = mask;
                        }
                    }
                }
            }
        }
    }
    if (n & 1) {
        int ans = -1;
        int bestl, bestr;
        rep (i, P + 1) {
            if (f[n / 2][i][P - i] + mat[i][n / 2 + 1] + mat[P - i][n / 2 + 1] - (i == P - i ? mat[i][n / 2 + 1] : 0) > ans) {
                ans = f[n / 2][i][P - i] + mat[i][n / 2 + 1] + mat[P - i][n / 2 + 1] - (i == P - i ? mat[i][n / 2 + 1] : 0);
                bestl = i;
                bestr = P - i;
            }
            if (P - i > 0
             && f[n / 2][i][P - i - 1] + mat[i + 1][n / 2 + 1] + mat[P - i][n / 2 + 1] - (i + 1 == P - i ? mat[i + 1][n / 2 + 1] : 0) > ans) {
                ans = f[n / 2][i][P - i - 1] + mat[i + 1][n / 2 + 1] + mat[P - i][n / 2 + 1] - (i + 1 == P - i ? mat[i + 1][n / 2 + 1] : 0);
                bestl = i;
                bestr = P - i - 1;
            }
        }
        s[n / 2 + 1] = P - bestl - bestr;
        rec(n / 2, bestl, bestr);
    } else {
        int ans = -1;
        int bestl, bestr;
        rep (i, P + 1) {
            if (f[n / 2][i][P - i] > ans) {
                ans = f[n / 2][i][P - i];
                bestl = i;
                bestr = P - i;
            }
        }
        rec(n / 2, bestl, bestr);
    }
    for (int i = 1; i <= n; i++)
        putchar(s[i] ? 'P' : 'Q');
    puts("");
}

const int A = 9705276 / 2;
const int B = 12805858 / 2;

int main() {
    freopen("identification.in", "r", stdin);
    freopen("identification.out", "w", stdout);
	ll x, y;
	ext_gcd<ll>(A, B, x, y);
	scanf("%d", &n);
	ll maxpeak = -1;
	rep (i, n) {
	    double x;
	    scanf("%lf", &x);
	    w[i] = (ll)(x * 100000 + 0.5);
	    checkmax(maxpeak, w[i]);
	}
	maxpeak /= 2;
	P = (maxpeak * x % B + B) % B;
	Q = (maxpeak - A * P) / B;
	int m = 0;
	rep (i, n) {
	    if (w[i] & 1 || (w[i] / 2 * x % B + B) % B > P || (w[i] / 2 - A * P) / B > Q) continue;
	    w[m++] = w[i];
	}
	n = m;
	memset(mat, 0, sizeof(mat));
	rep (i, n) {
	    a[i] = (w[i] / 2 * x % B + B) % B;
	    b[i] = (w[i] / 2 - A * a[i]) / B;
	    mat[a[i]][a[i] + b[i]] = 1;
	}
	dp();
}