Submission #378414

#	Time	Username	Problem	Language	Result	Execution time	Memory
378414		Karliver	Three Friends (BOI14_friends)	C++14	0 / 100	1074 ms	9560 KiB

friends

#include <bits/stdc++.h>
#include <fstream>
#define FIXED_FLOAT(x)  std::fixed <<std::setprecision(20) << (x)
#define all(v) (v).begin(), (v).end()
using namespace  std;
#define forn(i,n) for (int i = 0; i < (n); ++i)
using ll = long long;
int mod = (ll)1e9 + 7;
#define PI acos(-1)
typedef pair<int, int> pairs;
typedef complex<ll> G;
const int INF = 1e9 + 1;
const int N = 100;
const double eps = 1e-3;

template <typename XPAX>
void ckma(XPAX &x, XPAX y) {
    x = (x < y ? y : x);
}
template <typename XPAX>
void ckmi(XPAX &x, XPAX y) {
    x = (x > y ? y : x);
}


ll power(ll a, ll b){
    if(!b)
        return 1;
    ll c=power(a,b/2);
    c=(1LL*c*c);
    if(b%2)
        c=(1LL*c*a);
    return c;
}


int mul(int a, int b) {
    return a * 1ll * b % mod;
}
int add(int a, int b) {
    int s = (a+b);
    if (s>=mod) s-=mod;
    return s;
}



struct RMQ {
    vector<vector<int>>st;
    RMQ(vector<int> &a) {
        int n = a.size();
        int k = ceil(log2(n));
        st.clear();
        st = vector<vector<int>>(n, vector<int>(k + 1, 0));
        for(int i = 0;i < n;++i) {
            st[i][0] = a[i];
        }
        for(int j = 1;j <= k;++j) {
            for(int i = 0;i + (1 << j) <= n;++i) {
                st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
            }
        }

    }
    int rng_q(int l, int r) {
        if(l > r)return -1;
        int j = log2(r - l + 1);
        int ans = max(st[l][j], st[r - (1 << j) + 1][j]);
        return ans;
    }

};

template<long long mod = 1000000007>
struct modint{
	long long a;

	modint() : a(0){}
	modint(long long t){
		a = t % mod;
		if(a < 0) a += mod;
	}

	operator long long() const{ return a; }

	bool operator==(const modint &x) const{ return a == x.a; }
	bool operator!=(const modint &x) const{ return a != x.a; }

	modint operator-() const{ return modint(a ? (mod - a) : 0); }
	modint operator~() const{ return pow(mod - 2); }

	modint operator+(const modint &x) const{ return modint(*this) += x; }
	modint operator-(const modint &x) const{ return modint(*this) -= x; }
	modint operator*(const modint &x) const{ return modint(*this) *= x; }
	modint operator/(const modint &x) const{ return modint(*this) /= x; }

	modint &operator+=(const modint &x){
		a += x.a;
		if(a >= mod) a -= mod;
		return *this;
	}
	modint &operator-=(const modint &x){
		a -= x.a;
		if(a < 0) a += mod;
		return *this;
	}
	modint &operator*=(const modint &x){
		a = a * x.a % mod;
		return *this;
	}
	modint &operator/=(const modint &x){
		a = a * (~x).a % mod;
		return *this;
	}

	friend ostream &operator<<(ostream &os,const modint &x){
		return os << x.a;
	}
	friend istream &operator>>(istream &is,modint &x){
		long long t;
		is >> t;
		x = modint(t);
		return is;
	}

	modint pow(long long x) const{
		modint ret = 1,tmp = a;
		for(;x;tmp *= tmp,x >>= 1){
			if(x & 1) ret *= tmp;
		}
		return ret;
	}
};
const ll MOD = 1e9 + 7;
using Mint = modint<MOD>;


template<class T>
struct Combination{
	vector<T> fact,factinv;
	Combination(int n) : fact(n + 1),factinv(n + 1){
		fact[0] = 1;
		for(int i = 1;i <= n;i++) fact[i] = fact[i - 1] * T(i);
		factinv[n] = ~fact[n];
		for(int i = n;i >= 1;i--) factinv[i - 1] = factinv[i] * T(i);
	}
	T nCr(int n,int r){
		if(n < 0 || r < 0 || n < r) return 0;
		return fact[n]  * factinv[r] *  factinv[n - r];
	}
	T factorial(int x) {
        if(x < 0)return 0;
        return fact[x];
	}
};

void done() {


}


void solve()
{



    // 11000
    //
    // 4 3 5 2 1
    // -1 2 -3 -1
    //

    int n;
    cin >> n;
    string s;
    cin >> s;
    
    int cnt = 0;
    string ans = "";
    auto work = [&](string t) {
        string fir = t.substr(0, n / 2);

        string lst = t.substr(n / 2, n / 2);
        if(fir == lst) {
            ++cnt;
            ans = fir;
        }
    };

    forn(i, n) {
        string p = s;
        p.erase(p.begin() + i);
        work(p);
    }
    if(cnt == 0) {
        cout << "NOT POSSIBLE" << '\n';
        return;
    }
    if(cnt > 1) {
        cout << "NOT UNIQUE" << '\n';
        return;
    }
    cout << ans << '\n';


}

void emer() {





    // 3 4
    // 3 4 5
    //

    //
    // x + y = w + z
    // x =  w + z - y
    //
    int n;
    cin >> n;
    for(int i = 1;i <= 9;++i) cout << n * i << '\n';
}

void another() {

    // 10011
    //
    int n, q;
    cin>> n >> q;
    vector<int> c(n);
    for(int i = 0;i < n;++i) {
        cin >> c[i];
    }

    vector<vector<pair<int, pairs>>> qur(n);
    for(int i = 0;i < q;++i) {
        int l, r;
        cin>> l >> r;
        --l;
        --r;
        qur[r].push_back({l, {i, 1}});
        if(l) {
            qur[l - 1].push_back({l, {i, -1}});
        }
    }
    vector<int> f(n);

    auto inc = [&](int x) {
        for(; x < n;x = (x | (x + 1))) f[x]++;
    };
    auto get = [&](int  x) {
        int ans =0;
        for(; x >= 0;x = (x & (x + 1)) - 1)
            ans += f[x];
        return ans;
    };

    vector<int> ret(q);
    map<int, int> last;
    vector<int> pev(n, -1);

    for(int i = 0;i < n;++i) {
        if(last.count(c[i])) {
            pev[i] = last[c[i]];
        }
        last[c[i]] = i;
        inc(pev[i] + 1);
        for(auto c : qur[i]) {
            ret[c.second.first] += get(c.first) * c.second.second;
            //cout << ret[c.second.first] << '\n';

        }
    }

    forn(i, q) cout << ret[i] << '\n';

    // 1 6 4 1 2 2 8
    // (1, 3) (2, 5)
    // 3 0 0 0 0 0 0


}
void test_case() {
    int t;
    cin >> t;
    forn(p, t) {
        //cout << "Case #" << p + 1 << ": ";

        solve();

    }
}
int main() {



    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();





}

• Subtask 1: 0 / 35
• Subtask 2: 0 / 65