Submission #109115

#	Time	Username	Problem	Language	Result	Execution time	Memory
109115		MetB	Miners (IOI07_miners)	C++14	84 / 100	1555 ms	5248 KiB

miners

#include <iostream>
#include <cstdlib>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <bitset>
#include <queue>
#include <math.h>
#include <stack>
#include <vector>
#include <string.h>
#include <random>
 
typedef long long ll;
 
const ll MOD = 1e9 + 7, INF = 1e18;
 
using namespace std;
 
int n;

int enc (string a)
{
	if (a == "") return 0;
	if (a == "M") return 1;
	if (a == "B") return 2;
	if (a == "F") return 3;
	if (a == "MM") return 4;
	if (a == "MB") return 5;
	if (a == "MF") return 6;
	if (a == "BM") return 7;
	if (a == "BB") return 8;
	if (a == "BF") return 9;
	if (a == "FM") return 10;
	if (a == "FB") return 11;
	if (a == "FF") return 12;
}

string dec (int a)
{
	if (a == 0) return "";
	if (a == 1) return "M";
	if (a == 2) return "B";
	if (a == 3) return "F";
	if (a == 4) return "MM";
	if (a == 5) return "MB";
	if (a == 6) return "MF";
	if (a == 7) return "BM";
	if (a == 8) return "BB";
	if (a == 9) return "BF";
	if (a == 10) return "FM";
	if (a == 11) return "FB";
	if (a == 12) return "FF";
}

int encode (pair <string, string> s)
{
	return enc (s.first) * 13 + enc (s.second);
}

pair <string, string> decode (int s)
{
	return make_pair (dec (s / 13), dec (s % 13));
}
 
pair <string, int> transfer (pair <string, int> s, char a)
{
	string t;
	s.first += a;
 
	string k = s.first;
 
	k += a;
 
	sort (k.begin(), k.end());
 
	int v = k.length ();
 
	for (int i = 0; i < k.length (); i++)
		if (k[i] == k[i-1]) v--;
 
	if (s.first.length () == 3)
		for (int i = 1; i < s.first.length (); i++)
			t += s.first[i];
	else t = s.first;
 
	return {t, v + s.second};
}
 
map <int , int> d[100000];
 
int main ()
{
	cin >> n;
 
	string s;
 
	cin >> s;
 
	string h (1, s[0]);
 
	d[0][encode ({h, ""})] = 1;
 
	int mx = 0;
 
	for (int i = 1; i < s.length (); i++)
	{
		for (auto it : d[i-1])
		{
			auto sd = decode (it.first);
			auto k1 = transfer ({sd.first, it.second}, s[i]);
			auto k2 = transfer ({sd.second, it.second}, s[i]);
 
			mx = max (mx, k1.second);
			mx = max (mx, k2.second);
 
			auto v = d[i].find (encode (make_pair (k1.first, sd.second)));
			if (v == d[i].end ()) d[i][encode (make_pair (k1.first, sd.second))] = k1.second;
			else d[i][encode (make_pair (k1.first, sd.second))] = max (k1.second, v -> second);
 
			v = d[i].find (encode (make_pair (sd.first, k2.first)));
			if (v == d[i].end ()) d[i][encode (make_pair (sd.first, k2.first))] = k2.second;
			else d[i][encode (make_pair (sd.first, k2.first))] = max (k2.second, v -> second);
		}
 
		d[i-1].clear ();
	}
 
	cout << mx;
}

Compilation message (stderr)

miners.cpp: In function 'std::pair<std::__cxx11::basic_string<char>, int> transfer(std::pair<std::__cxx11::basic_string<char>, int>, char)':
miners.cpp:80:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < k.length (); i++)
                  ~~^~~~~~~~~~~~~
miners.cpp:84:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i < s.first.length (); i++)
                   ~~^~~~~~~~~~~~~~~~~~~
miners.cpp: In function 'int main()':
miners.cpp:107:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < s.length (); i++)
                  ~~^~~~~~~~~~~~~
miners.cpp: In function 'int enc(std::__cxx11::string)':
miners.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
miners.cpp: In function 'std::__cxx11::string dec(int)':
miners.cpp:55:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 7 / 7
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 0 / 8
• Subtask 12: 0 / 8