oj.uz

Submission #110391

# Submission time Handle Problem Language Result Execution time Memory
110391 2019-05-10T19:04:57 Z pamaj Exhibition (JOI19_ho_t2) C++14
0 / 100
 2 ms 384 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 410;

int n;

bool check(string t)
{
	for(int i = 0; i < t.size(); i++)
		if(t[i] == t[i + 1]) return false;

	return true;
}

map<pair<int, string>, int> dp;

int solve(int num, string s)
{
	if(check(s)) return dp[{num, s}] = num;

	if(dp[{num, s}]) return dp[{num, s}];

	int melhor = 1e9;

	if(num == n) return 1e9;

	for(int i = 0; i < n - 1; i++)
	{
		string temp = s;

		swap(temp[i], temp[i + 1]);

		melhor = min(melhor, solve(num + 1, temp));
	}

	return dp[{num, s}] = melhor;
}

int main()
{
	cin >> n;

	string s;

	cin >> s;

	string t = s;

	sort(s.begin(), s.end());

	int ans = 1e9;

	do
	{
		if(check(s))
		{
			int num_dif = 0;

			for(int i = 0; i < n; i++)
				if(s[i] != t[i]) num_dif++;

			ans = min(ans, num_dif);
		} 
	} while(next_permutation(s.begin(), s.end()));

	//int ans = solve(0, s);

	cout << (ans == (int)1e9 ? -1 : ans) << "\n";

}

Compilation message

joi2019_ho_t2.cpp: In function 'bool check(std::__cxx11::string)':
joi2019_ho_t2.cpp:9:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0; i < t.size(); i++)
                 ~~^~~~~~~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Incorrect 2 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -