oj.uz

답안 #971667

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
971667 2024-04-29T07:14:06 Z batsukh2006 세 명의 친구들 (BOI14_friends) C++17
100 / 100
 44 ms 6496 KB 
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<map>
#include<string>
#include<algorithm>
#include<vector>
#include<string.h>
#include<utility>
#include<set>
#include<cmath>
#include<queue>
#include<deque>
#include<functional>
#include<stack>
#include<limits.h>
#include<iomanip>
#include<unordered_map> 
#include<numeric>
#include<tuple>
#include<bitset>
using namespace std;
 
#define MOD 1000000007
#define int long long
#define endl '\n'
void solve(){
	int n; cin>>n;
	vector<char> u(n+1);
	for(int i=1; i<=n; i++) cin>>u[i];
	if(n%2==0){
		cout<<"NOT POSSIBLE";
	}else{
		int h=n/2;
		int cnt=0;
		vector<int> mp(26);
		for(int i=1; i<=h; i++){
			if(u[i]==u[i+h]) cnt++;
			else break;
		}
		for(int i=1; i<=n; i++) mp[u[i]-'A']++;
		int zero=0;
		for(int i=0; i<26; i++){
			if(mp[i]>0) zero++;
		}
		if(zero==1){
			for(int i=1; i<=n/2; i++) cout<<u[i];
		}else if(cnt==h&&u[1]==u[n]){
			cout<<"NOT UNIQUE";
		}else{
			int one=0,war=0,zero=0;
			for(int i=0; i<26; i++){
				if(mp[i]==1) one++;
				if(mp[i]%2==1) war++;
			}
			if(war>1){
				cout<<"NOT POSSIBLE";
			}else{
				if(one==1){
					vector<int> v;
					for(int i=1; i<=n; i++){
						if(mp[u[i]-'A']!=1) v.push_back(u[i]-'A');
					}
					int need=0;
					for(int i=0; i<n/2; i++){
						if(v[i]==v[i+h]) need++;
					}
					if(need==n/2){
						vector<char> s;
						for(int i=0; i<n/2; i++){
							char c=v[i]+'A';
							s.push_back(c);
						}
						for(int i=0; i<s.size(); i++) cout<<s[i];
					}else{
						cout<<"NOT POSSIBLE";
					}
				}else{
					vector<char> s;
					int i=1,j=n/2+1;
					while(i<=n/2+1&&j<=n){
						if(u[i]==u[j]){
							s.push_back(u[i]);
							i++;
							j++;
						}else{
							if(mp[u[i]-'A']%2==1){
								i++;
							}else if(mp[u[j]-'A']%2==1){
								j++;
							}else{
								break;
							}
						}
					}
					if(s.size()==n/2){
						for(int i=0; i<s.size(); i++) cout<<s[i];
					}else{
						s.clear();
						int i=1,j=n/2-1;
						while(i<=n/2&&j<=n){
							if(u[i]==u[j]){
								s.push_back(u[i]);
								i++;
								j++;
							}else{
								if(mp[u[i]-'A']%2==1){
									i++;
								}else if(mp[u[j]-'A']%2==1){
									j++;
								}else{
									war=1;
									break;
								}
							}
						}
						if(s.size()==n/2){
							for(int i=0; i<s.size(); i++) cout<<s[i];
						}else{
							s.clear();
							int i=1,j=n/2+2;
							while(i<=n/2+1&&j<=n){
								if(u[i]==u[j]){
									s.push_back(u[i]);
									i++;
									j++;
								}else{
									if(mp[u[i]-'A']%2==1){
										i++;
									}else if(mp[u[j]-'A']%2==1){
										j++;
									}else{
										war=1;
										break;
									}
								}
							}
							if(s.size()==n/2){
								for(int i=0; i<s.size(); i++) cout<<s[i];
							}else{
								cout<<"NOT POSSIBLE";
								return;
							}
						}
					}
				}
			}
		}
	}
}
signed main(){
    // freopen("file.in", "r", stdin);
    // freopen("file.out", "w", stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int T=1;
    // cin>>T;
    while(T--){
        solve();
        cout<<endl;
    }
    return 0;
}

Compilation message

friends.cpp: In function 'void solve()':
friends.cpp:74:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |       for(int i=0; i<s.size(); i++) cout<<s[i];
      |                    ~^~~~~~~~~
friends.cpp:96:17: warning: comparison of integer expressions of different signedness: 'std::vector<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   96 |      if(s.size()==n/2){
      |         ~~~~~~~~^~~~~
friends.cpp:97:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |       for(int i=0; i<s.size(); i++) cout<<s[i];
      |                    ~^~~~~~~~~
friends.cpp:117:18: warning: comparison of integer expressions of different signedness: 'std::vector<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  117 |       if(s.size()==n/2){
      |          ~~~~~~~~^~~~~
friends.cpp:118:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |        for(int i=0; i<s.size(); i++) cout<<s[i];
      |                     ~^~~~~~~~~
friends.cpp:138:19: warning: comparison of integer expressions of different signedness: 'std::vector<char>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
  138 |        if(s.size()==n/2){
      |           ~~~~~~~~^~~~~
friends.cpp:139:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  139 |         for(int i=0; i<s.size(); i++) cout<<s[i];
      |                      ~^~~~~~~~~
friends.cpp:51:20: warning: unused variable 'zero' [-Wunused-variable]
   51 |    int one=0,war=0,zero=0;
      |                    ^~~~

Subtask #1
35.0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 ms 464 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 0 ms 344 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 1 ms 348 KB Output is correct
27 Correct 1 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 344 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 344 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 1 ms 504 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 1 ms 344 KB Output is correct
43 Correct 1 ms 344 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 348 KB Output is correct
46 Correct 0 ms 348 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 0 ms 352 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 0 ms 344 KB Output is correct
51 Correct 0 ms 344 KB Output is correct
52 Correct 0 ms 352 KB Output is correct
53 Correct 0 ms 352 KB Output is correct
54 Correct 0 ms 348 KB Output is correct

Subtask #2
65.0 / 65.0

# 결과 실행 시간 메모리 Grader output
1 Correct 38 ms 6380 KB Output is correct
2 Correct 38 ms 6348 KB Output is correct
3 Correct 41 ms 6496 KB Output is correct
4 Correct 44 ms 6348 KB Output is correct
5 Correct 37 ms 6240 KB Output is correct
6 Correct 18 ms 4184 KB Output is correct
7 Correct 39 ms 5336 KB Output is correct
8 Correct 18 ms 3928 KB Output is correct
9 Correct 34 ms 5644 KB Output is correct
10 Correct 35 ms 5836 KB Output is correct
11 Correct 24 ms 4816 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 452 KB Output is correct
14 Correct 0 ms 344 KB Output is correct
15 Correct 0 ms 344 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 380 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 452 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 0 ms 348 KB Output is correct
36 Correct 1 ms 348 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 1 ms 344 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 0 ms 348 KB Output is correct
45 Correct 0 ms 348 KB Output is correct
46 Correct 0 ms 344 KB Output is correct
47 Correct 1 ms 348 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 1 ms 348 KB Output is correct
50 Correct 0 ms 348 KB Output is correct
51 Correct 0 ms 348 KB Output is correct
52 Correct 0 ms 348 KB Output is correct
53 Correct 0 ms 348 KB Output is correct
54 Correct 0 ms 352 KB Output is correct