CSES - Datatähti 2018 alku - Results
Submission details
Task:Merkkijono
Sender:Ilmari2000
Submission time:2017-10-15 22:24:09 +0300
Language:C++
Status:READY
Result:0
Feedback
groupverdictscore
#10
Test results
testverdicttime
#10.06 sdetails
#2ACCEPTED0.05 sdetails
#3ACCEPTED0.06 sdetails
#40.05 sdetails
#50.07 sdetails
#60.05 sdetails
#70.07 sdetails
#80.07 sdetails
#90.06 sdetails
#100.06 sdetails

Compiler report

input/code.cpp: In function 'int go(int, state, std::stack<int>*)':
input/code.cpp:37:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(s.route.length() > shortest)
                        ^
input/code.cpp:48:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if(s.route.length() < shortest)
                         ^

Code

#include <iostream>
#include <stack>
#include <vector>

#include <limits.h>

using namespace std;

struct state
{
	long long int p0;
	long long int p1;
	long long int nodes;
	string route;
};

int target;
int shortest = INT_MAX;
string final;

int go(int dir, state s, stack<int>* res)
{
	if(dir)
	{
		s.p0 += s.p1;
		s.nodes += s.p1;
	}
	else
	{
		s.p1 += s.p0;
		s.nodes += s.p0;
	}

	//cout << "dir: " << dir << ", p0: " << s.p0 << ", p1: " << s.p1 << ", nodes: " << s.nodes << endl;
	//cout << s.route << endl;
	s.route += (dir ? "1" : "0");
	if(s.route.length() > shortest)
		return 0;

	if(s.nodes > target)
	{
		//cout << "fuck" << endl;
		return 0;
	}

	if(s.nodes == target)
	{
		if(s.route.length() < shortest)
			shortest = s.route.length();
		//cout << s.route << ", " << shortest << endl;
		final = s.route;
		return 0;
	}

	if(!go(!dir, s, res))
	{
		return go(dir, s, res);
	}
	return 0;
}

int main()
{
	cin >> target;

	stack<int> result;
	go(0, {1, 1, 0, ""}, &result);

	cout << final << endl;
}

Test details

Test 1

Verdict:

input
ABABABABABABABABABABABABABABAB...

correct output
ABABABABABABABABABABABABABABAB...

user output
(empty)

Test 2

Verdict: ACCEPTED

input
AABBAABBAABBAABBAABBAABBAABBAA...

correct output
(empty)

user output
(empty)

Test 3

Verdict: ACCEPTED

input
ABABABABABABABABABABABABABABAB...

correct output
(empty)

user output
(empty)

Test 4

Verdict:

input
BBABABBBBBAABBBABABABBBBAAABAB...

correct output
BAB

user output
(empty)

Test 5

Verdict:

input
ACDCBBACDBBBACAACBBDBADBAABABA...

correct output
ACDCACDADBADABACACDCADADABABCA...

user output
(empty)

Test 6

Verdict:

input
EETFHIJOGACDHMGVFJCMETMZDEITTR...

correct output
TFHIJOGACDHMGVFJCMETMZDEIROTET...

user output
(empty)

Test 7

Verdict:

input
GOONLAHLYPRFCZKIKSJWAWWYJJPCDB...

correct output
GNLAHLYPRFCZKIKSJWAYPCDNWYMRCE...

user output
(empty)

Test 8

Verdict:

input
PISHWMOTCDDZFRMYMOMYDYYGJZIQHS...

correct output
PISHWMOTCZFRMYMOMYDGJZIQHSVAOK...

user output
(empty)

Test 9

Verdict:

input
QUVVTPXAMWWODFXRONJODPGBTCISGM...

correct output
QUTPXAMODFXRONJODPGBTCISGMVRBW...

user output
(empty)

Test 10

Verdict:

input
POXHAHYEZTLYNFSLABODMRNKDSKROZ...

correct output
POXHAHYEZTLYNFSLABODMRNKDSKROZ...

user output
(empty)