Submission #498476

#	Time	Username	Problem	Language	Result	Execution time	Memory
498476		Hi_Im_Not_Meo_Meo	Type Printer (IOI08_printer)	C++14	10 / 100	47 ms	44216 KiB

printer

#include"bits/stdc++.h"
#define f(i,j,k) for(int i=j;i<=k;i++)
#define pb push_back

const int N = 3e4;
using namespace std;
int n;
bool cx[N];
string s[N];
vector<int> f[N], ans;

struct Node{
	int vt;
	Node* child[30];
	Node(){ 
		vt = 0;
		f(i,0,29) child[i] = nullptr; 
	}
};

struct Trie{
	Node *root;
	Trie(){ root = new Node;}
	void __up(int i){
		int trc = 0, vvt = -1;
		Node *it = root;
		for(auto ii : s[i]){
			int j = (int) ii - 'a';
			if(!it->child[j]) it->child[j] = new Node;
			else trc = it->child[j]->vt;
			it = it->child[j];
			it->vt = i;
		}
		f[trc].pb(i);
	}
}lxv;

void dfs(int u,int pre){
	ans.pb(u);
	for(auto v: f[u]) dfs(v,u);
}

main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	memset(cx,true,sizeof(cx));
	cin>>n;
	f(i,1,n) cin>>s[i];
	sort(s+1,s+1+n);
	//f(i,1,n) cout<<s[i]<<endl;
	f(i,1,n) lxv.__up(i);
	f(i,0,n) sort(f[i].begin(),f[i].end(),[](int u,int v){
		return s[u].size() < s[v].size();
	});
	dfs(0,-1);
	vector<char> kq;
	f(i,0,s[ans[1]].size()-1) kq.pb(s[ans[1]][i]);
	kq.pb('P');
	f(i,2,n){
		bool ok = true;
		int u = ans[i-1], v = ans[i], vt = -1;
		f(i,0,s[u].size()-1)
			if(!ok) kq.pb('-');
			else if(s[u][i] != s[v][i]){ kq.pb('-'), ok = false;}
			else vt = i;
		f(i,vt+1,s[v].size()-1) kq.pb(s[v][i]);
		kq.pb('P');
	}
	cout<<kq.size()<<'\n';
	for(auto v: kq) cout<<v<<'\n';
}

Compilation message (stderr)

printer.cpp: In member function 'void Trie::__up(int)':
printer.cpp:25:16: warning: unused variable 'vvt' [-Wunused-variable]
   25 |   int trc = 0, vvt = -1;
      |                ^~~
printer.cpp: At global scope:
printer.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   43 | main(){
      | ^~~~
printer.cpp: In function 'int main()':
printer.cpp:2:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define f(i,j,k) for(int i=j;i<=k;i++)
......
   56 |  f(i,0,s[ans[1]].size()-1) kq.pb(s[ans[1]][i]);
      |    ~~~~~~~~~~~~~~~~~~~~~~      
printer.cpp:56:2: note: in expansion of macro 'f'
   56 |  f(i,0,s[ans[1]].size()-1) kq.pb(s[ans[1]][i]);
      |  ^
printer.cpp:2:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define f(i,j,k) for(int i=j;i<=k;i++)
......
   61 |   f(i,0,s[u].size()-1)
      |     ~~~~~~~~~~~~~~~~~          
printer.cpp:61:3: note: in expansion of macro 'f'
   61 |   f(i,0,s[u].size()-1)
      |   ^
printer.cpp:2:31: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    2 | #define f(i,j,k) for(int i=j;i<=k;i++)
......
   65 |   f(i,vt+1,s[v].size()-1) kq.pb(s[v][i]);
      |     ~~~~~~~~~~~~~~~~~~~~       
printer.cpp:65:3: note: in expansion of macro 'f'
   65 |   f(i,vt+1,s[v].size()-1) kq.pb(s[v][i]);
      |   ^

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