oj.uz

답안 #879530

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
879530 2023-11-27T15:27:36 Z ThylOne 세 명의 친구들 (BOI14_friends) C++14
0 / 100
 51 ms 24160 KB 
#include<bits/stdc++.h>

using namespace std;
const int maxiN=200001;
const int LOG = 21;
int n,L;
string ans;
int nbSolLU(string lower,string upper,int b=0){
    bool comp[L][2];
    for(int i=0;i<L;i++){
        comp[i][0] = (upper[i]==lower[i]);
        comp[i][1] = (upper[i+1]==lower[i]);
    }
    int prefix[L];
    int suffix[L];
    int actSum=0;
    for(int i=0;i<L;i++){
        actSum+=comp[i][0];
        prefix[i] = actSum;
    }
    actSum=0;
    for(int i=L-1;i>=0;i--){
        actSum+=comp[i][1];
        suffix[i] = actSum;
    }
    int nbSol=0;
    for(int i=b;i<L+1;i++){
        int pts = 0;
        if(i>0)pts+=prefix[i-1];
        if(i<L-1)pts+=suffix[i];
        if(pts==L){
            if(ans==""){
                for(int j=0;j<L+1;j++){
                    if(j!=i)ans+=upper[j];
                }
            }
            nbSol++;
        }
    }
    return nbSol;
}
signed main(){
    n;cin>>n;
    if(n%2==0){
        cout<<"NOT POSSIBLE\n";
        return 0;
    }
    L = (n-1)/2;
    string line;cin>>line;
    string upper="";
    string lower="";
    for(int i=0;i<=L;i++){
        upper+=line[i];
    }
    for(int i=L+1;i<n;i++){
        lower+=line[i];
    }
    

    int nbSol=0;
    nbSol+=nbSolLU(lower,upper);
    upper="";
    lower="";
    for(int i=L;i<n;i++){
        upper+=line[i];
    }
    for(int i=0;i<L;i++){
        lower+=line[i];
    }
    nbSol+=nbSolLU(lower,upper,1);
    if(nbSol==1){
        cout<<ans<<endl;
    }else if(nbSol==0){
        cout<<"NOT POSSIBLE"<<endl;
    }else{
        cout<<"NOT UNIQUE"<<endl;
    }
   
    return 0;
}

Compilation message

friends.cpp: In function 'int main()':
friends.cpp:43:5: warning: statement has no effect [-Wunused-value]
   43 |     n;cin>>n;
      |     ^

Subtask #1
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 23980 KB Output is correct
2 Correct 51 ms 24160 KB Output is correct
3 Correct 50 ms 22716 KB Output is correct
4 Correct 51 ms 23480 KB Output is correct
5 Incorrect 48 ms 22208 KB Output isn't correct
6 Halted 0 ms 0 KB -