Submission 1430 | MatCom Online Grader

Id	Date	User	Problem	Result	Time	Mem	Lang
1430	29/05/2013 15:44:00	rlac	D - Descendencia del rey	Accepted	234	24.4 KiB	GNU G++ 5.1.0

Code

#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>

#ifdef RLAC
	#define DEB(a)			clog << __LINE__ << ": " << #a << " = " << (a) << endl
	#define OUT(a, n)		for (int J = 0; J < (n); ++J)	clog << (a)[J] << " \n"[J == (n) - 1];
	#define NAME			"D"
#else
	#define DEB(a)
	#define OUT(a, n)
#endif

using namespace std;

const int MAXN = 5e6 + 5;
char s[MAXN];
int pref[MAXN], n, ans;

void build_pref ()
{
	pref[0] = n;
	int g = 0, f;
	
	for (int i = 1; s[i]; ++i)
	{
		if (i < g && pref[i - f] != g - i)
		    pref[i] = min(pref[i - f], g - i);
		else
		{
			for (g = max(g, i), f = i; s[g] == s[g - f]; ++g);
			
			pref[i] = g - f;
		}
	}
}

int main ()
{
	//Improvement region
	ios_base::sync_with_stdio(0);
	cin.tie(0);

//Input region
	#ifdef RLAC
		system("notepad "NAME".in");
		freopen(NAME".in", "r", stdin);
		FILE * FILE_NAME = freopen(NAME".out", "w", stdout);
		int TIME = clock();
	#endif
	//Add your code here...
	cin >> s;
	n = strlen(s);
	build_pref();	
	
	for (int i = 1; i < n; ++i)
	{
		int len = pref[i];
		
		if (s[i + len] < s[len])
			++ans;
	}
	
	cout << ans << endl;
	//Output region
	#ifdef RLAC
		cout << flush;
		clog << clock() - TIME << endl;
		fclose(FILE_NAME);
		system("notepad "NAME".out");
	#endif
	return 0;
}

Judgement Details

Case#0: [25538560 bytes] [46 ms] ok "0"

Case#1: [25534464 bytes] [31 ms] ok "0"

Case#2: [25534464 bytes] [31 ms] ok "3"

Case#3: [25534464 bytes] [15 ms] ok "3"

Case#4: [25534464 bytes] [31 ms] ok "5"

Case#5: [25534464 bytes] [15 ms] ok "1"

Case#6: [25534464 bytes] [31 ms] ok "2"

Case#7: [25534464 bytes] [31 ms] ok "4"

Case#8: [25538560 bytes] [15 ms] ok "4"

Case#9: [25530368 bytes] [15 ms] ok "9"

Case#10: [25534464 bytes] [31 ms] ok "8"

Case#11: [25530368 bytes] [234 ms] ok "9"

Case#12: [25534464 bytes] [15 ms] ok "17"

Case#13: [25530368 bytes] [31 ms] ok "11"

Case#14: [25534464 bytes] [31 ms] ok "53"

Case#15: [25530368 bytes] [31 ms] ok "6"

Case#16: [25530368 bytes] [31 ms] ok "29"

Case#17: [25534464 bytes] [31 ms] ok "8"

Case#18: [25534464 bytes] [31 ms] ok "0"

Case#19: [25530368 bytes] [15 ms] ok "2"

Case#20: [25534464 bytes] [31 ms] ok "0"

Case#21: [25530368 bytes] [31 ms] ok "12"

Case#22: [25534464 bytes] [15 ms] ok "384"

Case#23: [25526272 bytes] [31 ms] ok "49999"

Case#24: [25530368 bytes] [31 ms] ok "17"

Case#25: [25538560 bytes] [31 ms] ok "33333"

Case#26: [25534464 bytes] [31 ms] ok "3078"

Case#27: [25534464 bytes] [31 ms] ok "24999"

Case#28: [25534464 bytes] [31 ms] ok "19663"

Case#29: [25526272 bytes] [31 ms] ok "99999"

Case#30: [25530368 bytes] [46 ms] ok "196620"

Case#31: [25530368 bytes] [15 ms] ok "16666"

Case#32: [25530368 bytes] [31 ms] ok "14045"

Case#33: [25530368 bytes] [15 ms] ok "99999"

Case#34: [25534464 bytes] [31 ms] ok "98304"

Case#35: [25530368 bytes] [31 ms] ok "49999"

Case#36: [25534464 bytes] [31 ms] ok "1198"

Case#37: [25534464 bytes] [31 ms] ok "66666"

Case#38: [25534464 bytes] [31 ms] ok "152"

Case#39: [25530368 bytes] [31 ms] ok "89999"

Case#40: [25534464 bytes] [31 ms] ok "107242"

Case#41: [25534464 bytes] [31 ms] ok "54544"

Case#42: [25530368 bytes] [15 ms] ok "2307"

Case#43: [25530368 bytes] [31 ms] ok "83331"

Case#44: [25534464 bytes] [31 ms] ok "1423"

Case#45: [25526272 bytes] [31 ms] ok "38460"

Case#46: [25530368 bytes] [46 ms] ok "3511"

Case#47: [25534464 bytes] [31 ms] ok "57141"

Case#48: [25530368 bytes] [31 ms] ok "820"

Case#49: [25530368 bytes] [31 ms] ok "13332"

Case#50: [25530368 bytes] [31 ms] ok "3072"

Case#51: [25534464 bytes] [31 ms] ok "6249"

Case#52: [25534464 bytes] [31 ms] ok "5064"

Case#53: [25534464 bytes] [31 ms] ok "35292"

Case#54: [25534464 bytes] [31 ms] ok "5808"

Case#55: [25530368 bytes] [31 ms] ok "11110"

Case#56: [25534464 bytes] [15 ms] ok "85"

Case#57: [25534464 bytes] [31 ms] ok "68419"

Case#58: [25538560 bytes] [31 ms] ok "43"

Case#59: [25534464 bytes] [46 ms] ok "44999"

Case#60: [25534464 bytes] [31 ms] ok "216"

Case#61: [25530368 bytes] [31 ms] ok "61903"

Case#62: [25534464 bytes] [31 ms] ok "910"

Case#63: [25534464 bytes] [46 ms] ok "22725"

Case#64: [25534464 bytes] [31 ms] ok "4542"

Case#65: [25534464 bytes] [31 ms] ok "4347"

Case#66: [25534464 bytes] [31 ms] ok "196612"

Case#67: [25534464 bytes] [31 ms] ok "45828"

Case#68: [25530368 bytes] [31 ms] ok "30"

Case#69: [25534464 bytes] [46 ms] ok "83999"

Case#70: [25530368 bytes] [15 ms] ok "7"

Case#71: [25534464 bytes] [46 ms] ok "42306"

Case#72: [25530368 bytes] [234 ms] ok "0"

Case#73: [25534464 bytes] [218 ms] ok "0"

Case#74: [25530368 bytes] [234 ms] ok "4999999"

Case#75: [25530368 bytes] [218 ms] ok "4999999"

Case#76: [25530368 bytes] [218 ms] ok "4999999"

Matcom Online Grader