oj.uz

Submission #120110

# Submission time Handle Problem Language Result Execution time Memory
120110 2019-06-23T11:26:35 Z arthurconmy Type Printer (IOI08_printer) C++17
100 / 100
 161 ms 50236 KB 
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <map>
#include <queue>
#include <bitset>
#include <random>
#include <stack>
#include <deque>
#include <chrono>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef pair<int,int> pii;
#define REP(i, a, b) for (int i = int(a); i <= int(b); i++)
#define REPb(j, d, c) for (int j = int(d); j >= int(c); j--)
#define ff first
#define ss second
#define pb push_back
#define endl "\n"

vector<char> all_actions;

int trie[int(6e5)][26];
bool is_end[int(6e5)];
bool is_long[int(6e5)];

bool comper(string a, string b)
{
	if(a.size() < b.size()) return true;
	if(a.size() > b.size()) return false;

	REP(i,0,a.size()-1)
	{
		if((int)a[i] > (int)b[i])
		{
			return false;
		}

		if((int)a[i] < (int)b[i])
		{
			return true;
		}
	}

	return true;
}

void dfs(int v)
{
	if(is_end[v]) all_actions.pb('P'); // cout << "P" << endl;

	pii loong = {-1,-1};

	REP(i,0,25)
	{
		if(trie[v][i]!=0)
		{
			if(is_long[trie[v][i]])
			{
				loong = {v,i};
				continue; 
			}

			all_actions.pb((char)(i+97)); // cout << (char)(i+97) << endl;

			dfs(trie[v][i]);
		}
	}

	if(loong.ff != -1)
	{
		all_actions.pb((char)(loong.ss+97)); // cout << (char)(loong.ss+97) << endl;

		dfs(trie[loong.ff][loong.ss]);
	}

	all_actions.pb({'-'}); // cout << "-" << endl;
}

int main() // LL OR INT?? DELETED IFSTREAM??
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	//ifstream cin("input.txt");
	//ifstream cin("test.in");
	//ofstream cout("test.out");

	int n;
	cin>>n;

	vector<string> words;

	REP(i,1,n)
	{
		string w;
		cin>>w;

		words.pb(w);
	}

	sort(words.begin(),words.end(),comper);

	// build the trie

	int nex=1;

	REP(wi,0,n-1)
	{
		string w = words[wi];

		int len = w.size();
		int cur=0;

		REP(i,0,len-1)
		{
			if(trie[cur][(int)w[i]-97]!=0)
			{
				cur=trie[cur][(int)w[i]-97];
			}

			else
			{
				trie[cur][(int)w[i]-97]=nex;
				cur=nex;
				nex++;
			}

			if(i==len-1)
			{
				is_end[cur]=true;
			}

			if(wi==n-1)
			{
				is_long[cur] = true;
			}
		}
	}

	// Euler tour the trie

	dfs(0);

	int ans = all_actions.size()-1;

	while(all_actions[ans]=='-') ans--;

	cout << ans+1 << endl;

	REP(i,0,ans)
	{
		cout << all_actions[i] << endl; 
	} 
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 768 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1152 KB Output is correct
2 Correct 4 ms 1408 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3328 KB Output is correct
2 Correct 22 ms 6560 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 7932 KB Output is correct
2 Correct 18 ms 2464 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 19216 KB Output is correct
2 Correct 131 ms 42324 KB Output is correct
3 Correct 91 ms 23148 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 15468 KB Output is correct
2 Correct 161 ms 50236 KB Output is correct
3 Correct 109 ms 26228 KB Output is correct
4 Correct 153 ms 47596 KB Output is correct