글 읽기 - 선생님들 도와주세요..

extra1563 4년 전 1

제가 만든 반례 :

recrwrivxp ->ceiprvrrwx
ceiprvrrwx ->ceiprvrrwx
cummam -> acmumm
aabcccddffgggijjjjkklnnnovwwwxxz -> aabcccddffgggijjkkjjlnnnovwwwxxz
lnnrwwwxxz -> lnnrwxwwxz

에도 문제없이 돌아가는 것 같은데 알고리즘 어디가 문제일까요?

#include <bits/stdc++.h>
using namespace std;

int no, cnt;
vector<int> v;
int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	string p; cin >> p;
	sort(p.begin(), p.end());
	int n = p.length();
	for (int i = 0; i < n / 2; i++)
		if (p[i] == p[n - i - 1]) {
			cnt++;
			v.push_back(n - i - 1); // 대칭된 자리의 문자가 같다면 뒤문자의 인덱스를 저장
		}
	if (cnt != 0) {
		sort(v.begin(), v.end());
		int num = 0;
		for (int i = 0; i < v.size(); i++) {
			int l = v[i], swap_ok = 0;
			// 바꿔야하는 문자의 오른쪽부터 탐색
			for (int r = l + 1; !swap_ok && (r < n); r++) {
				// 바꿔야 하는 문자(p[l])가 
				// 1. 바꿀 문자(p[r])와 같은 문자가 아니며
				// 2. 바꿀 자리(r)에 대칭이 되는 자리의 문자(p[n-1-r])가 같지않으면 swap
				if (p[r] != p[l] && p[n - 1 - r] != p[l]) {
					swap(p[l], p[r]);
					swap_ok = 1;
				}
			}
			if (swap_ok) num++;
		}
		if (num != v.size()) no = 1;
	}
	if (no) cout << -1;
	else cout << p;
}

playsworld16 3년 전 3

만드신 반례 잘 썼습니다!

반례 드립니다.

input: aooovw

output: aoowvo

answer: aoovwo

extra1563 3년 전 1

감사합니다 :)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

선생님들 도와주세요..

extra1563 4년 전 1

playsworld16 3년 전 3

extra1563 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말