Submission #136011

#	Time	Username	Problem	Language	Result	Execution time	Memory
136011		Zex	Three Friends (BOI14_friends)	C++11	0 / 100	168 ms	148020 KiB

friends

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define INF INT_MAX
#define output for(int i=0;i<sizex;i++) { for(int j=0;j<sizey;j++) { cout << moveChart[i][j] << " "; }cout<<endl; }cout<<endl;

const int maxN = 2000001;
int dp[maxN][4]; // 0 noPluses  1 addLeft   2 addRight  3 addBoth
int bt[maxN][4];
int N;
string s;

int f( int idx, int mod ){

    int L = idx, R = idx+(N-1)/2;
    if( mod == 1 )      L++;
    else if( mod == 2 ) R++;
    else if( mod == 3 ) { L++; R++; }

    // cout << idx << " " << mod << " " << s[L] << " " << s[R] << endl;

    if( R == N && mod == 3 ) return 1;
    if( R == N ) return 0;

    if( dp[idx][mod] != -1 ) return dp[idx][mod];

    int res = 0;

    if( s[L] == s[R] ) { res += f( idx+1, mod ); 
        if( f( idx+1, mod ) == 1 ) bt[idx][mod] = 0;
    }

    if( mod == 3 ) res += 0; // not possible from here bro sorry
    if( mod == 2 ) { res += f( idx, 3 ); 
        if( f( idx, 3 ) == 1 ) bt[idx][mod] = 3;
    }
    if( mod == 1 ) {res += f( idx, 3 ); 
        if( f( idx, 3 ) == 1 ) bt[idx][mod] = 3;
    }
    if( mod == 0 ) { res += f( idx, 1 ) | f( idx, 2 ); 
        if( f( idx, 1 ) == 1 ) bt[idx][mod] = 1;
        if( f( idx, 2 ) == 1 ) bt[idx][mod] = 2;
    }

    return dp[idx][mod] = res;

}

int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    cin >> N >> s;

    if( !( N & 1 ) ){
        cout << "NOT POSSIBLE" << endl; return 0;
    }
    
    memset( dp, -1, sizeof dp );
    memset( bt, -1, sizeof bt );

    int res = f( 0, 0 );
    // cout << res << endl;

    // return 0;

    if( res == 0 ) cout << "NOT POSSIBLE" << endl;
    else if( res > 1 ) cout << "NOT UNIQUE" << endl;
    else{
    
        string out = "";
        int idx = 0, mod = 0;
        while( bt[idx][mod] != -1 ){

            int L = idx, R = idx+(N-1)/2;
            if( mod == 1 )      L++;
            else if( mod == 2 ) R++;
            else if( mod == 3 ) { L++; R++; }

            if( bt[idx][mod] == 0 ){
                out += s[L];
                idx++;
            }else if( bt[idx][mod] == 1 ){
                mod = 1;
            }else if( bt[idx][mod] == 2 ){
                mod = 2;
            }else if( bt[idx][mod] == 3 ){
                mod = 3;
            }else{
                cout << "WTF" << endl;
            }

        }

        cout << out << endl;

    } 

}

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