oj.uz

Submission #109188

# Submission time Handle Problem Language Result Execution time Memory
109188 2019-05-05T11:35:11 Z MetB Type Printer (IOI08_printer) C++14
100 / 100
 256 ms 85876 KB 
#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, ptr, printed;

string ans;

struct Node
{
	map <char, pair <int, int> > next;
	bool st;

} a[1000000];

void add (string s)
{
	int x = 0;

	for (int i = 0; i < s.length (); i++)
	{
		if (a[x].next.find (s[i]) == a[x].next.end ())
		{
			a[x].next[s[i]] = make_pair (ptr + 1, (int) s.length () - i);
			ptr++;
		}

		if (a[x].next[s[i]].second < (int) s.length () - i) 
			a[x].next[s[i]].second = (int) s.length () - i;
		x = a[x].next[s[i]].first;
	}

	a[x].st = true;
}

void dfs (int x)
{
	vector < pair <int, char> > v;

	if (a[x].st) 
	{
		ans += 'P';
		printed++;
	}

	for (pair <char, pair <int, int> > it : a[x].next)
		v.emplace_back (it.second.second, it.first);

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

	for (auto to : v)
	{

		ans += char (to.second);
		dfs (a[x].next[to.second].first);
	}

	if (printed < n) ans += '-';
}

int main ()
{
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		string s;
		cin >> s;

		add (s);
	}

	dfs (0);

	cout << ans.length () << endl;

	for (auto a : ans)
		printf ("%c\n", a);
}

Compilation message

printer.cpp: In function 'void add(std::__cxx11::string)':
printer.cpp:36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < s.length (); i++)
                  ~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 55160 KB Output is correct
2 Correct 54 ms 55160 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 55104 KB Output is correct
2 Correct 51 ms 55160 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 55160 KB Output is correct
2 Correct 52 ms 55132 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 55160 KB Output is correct
2 Correct 75 ms 55160 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 55160 KB Output is correct
2 Correct 52 ms 55416 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 55544 KB Output is correct
2 Correct 58 ms 55748 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 56928 KB Output is correct
2 Correct 76 ms 59000 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 59804 KB Output is correct
2 Correct 72 ms 56476 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 66560 KB Output is correct
2 Correct 224 ms 81020 KB Output is correct
3 Correct 166 ms 68600 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 64000 KB Output is correct
2 Correct 256 ms 85876 KB Output is correct
3 Correct 176 ms 70420 KB Output is correct
4 Correct 190 ms 84112 KB Output is correct