Submission #915578

#	Time	Username	Problem	Language	Result	Execution time	Memory
915578		josanneo22	Type Printer (IOI08_printer)	C++17	0 / 100	1084 ms	61016 KiB

printer

#include<bits/stdc++.h>
#include <random>
using namespace std;

namespace NEO {
	std::mt19937 cincai(std::chrono::steady_clock::now().time_since_epoch().count());
	using i64 = long long;

    #define pb push_back
    #define mp make_pair
    #define cs constexpr
    
    #define L(i,j,k) for(int i=(j);i<=(k);++i)
    #define R(i,j,k) for(int i=(j);i>=(k);--i)
    #define all(x) x.begin(),x.end()
    #define me(x,a) memset(x,a,sizeof(x))
    
    //~ #ifndef ONLINE_JUDGE
    //~ #include "debug.h"
    //~ #else
    //~ #define dbg(...) 43
    //~ #endif
}
using namespace NEO;

struct node {
	int nxt[26];
	bool is_longest, finish_word;
	node() {
		me(nxt, 0);
		is_longest = false;
		finish_word = false;
	}
};
cs int _N = 25000 * 21;
int tot = 0;
node trie[_N];

void build(string S) {
	int M = S.size(), P = 0;
	for (int i = 0; i < M; i++) {
		int nw = S[i] - 'a';
		if (trie[P].nxt[nw] == 0) {
			trie[P].nxt[nw] = ++tot;
			trie[tot] = node();
		}
		P = trie[P].nxt[nw];
	}
	trie[P].finish_word = true;
}
void paint(string S) {
	int P = 0;
	for (int i = 0; i < (int)S.size(); i++) {
		int nw = S[i] - 'a';
		P = trie[P].nxt[nw];
		trie[P].is_longest = true;
	}
}
string ans = "";
void dfs(int P) {
	int longest = -1;
	if (trie[P].finish_word) ans += 'P';
	for (int i = 0; i < 26; i++) {
		int next_node = trie[P].nxt[i];
		if (trie[next_node].is_longest) longest = i;
		else if (next_node != 0) {
			ans += (i + 'a');
			dfs(next_node);
		}
	}
	if (longest != -1) {
		ans += (longest + 'a');
		dfs(trie[P].nxt[longest]);
	}
	else if (longest == -1 && trie[P].is_longest) return;
	else ans += '-';
}
namespace fast {
    #pragma GCC optimize(Ofast)
    #pragma GCC optimization (unroll-loops)
    #pragma GCC target(avx,avx2,fma)
    #pragma GCC target(sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native)
    #pragma GCC optimize(3)
    #pragma GCC optimize("inline")
    #pragma GCC optimize("-fgcse")
    #pragma GCC optimize("-fgcse-lm")
    #pragma GCC optimize("-fipa-sra")
    #pragma GCC optimize("-ftree-pre")
    #pragma GCC optimize("-ftree-vrp")
    #pragma GCC optimize("-fpeephole2")
    #pragma GCC optimize("-ffast-math")
    #pragma GCC optimize("-fsched-spec")
    #pragma GCC optimize("unroll-loops")
    #pragma GCC optimize("-falign-jumps")
    #pragma GCC optimize("-falign-loops")
    #pragma GCC optimize("-falign-labels")
    #pragma GCC optimize("-fdevirtualize")
    #pragma GCC optimize("-fcaller-saves")
    #pragma GCC optimize("-fcrossjumping")
    #pragma GCC optimize("-fthread-jumps")
    #pragma GCC optimize("-funroll-loops")
    #pragma GCC optimize("-fwhole-program")
    #pragma GCC optimize("-freorder-blocks")
    #pragma GCC optimize("-fschedule-insns")
    #pragma GCC optimize("inline-functions")
    #pragma GCC optimize("-ftree-tail-merge")
    #pragma GCC optimize("-fschedule-insns2")
    #pragma GCC optimize("-fstrict-aliasing")
    #pragma GCC optimize("-fstrict-overflow")
    #pragma GCC optimize("-falign-functions")
    #pragma GCC optimize("-fcse-skip-blocks")
    #pragma GCC optimize("-fcse-follow-jumps")
    #pragma GCC optimize("-fsched-interblock")
    #pragma GCC optimize("-fpartial-inlining")
    #pragma GCC optimize("no-stack-protector")
    #pragma GCC optimize("-freorder-functions")
    #pragma GCC optimize("-findirect-inlining")
    #pragma GCC optimize("-fhoist-adjacent-loads")
    #pragma GCC optimize("-frerun-cse-after-loop")
    #pragma GCC optimize("inline-small-functions")
    #pragma GCC optimize("-finline-small-functions")
    #pragma GCC optimize("-ftree-switch-conversion")
    #pragma GCC optimize("-foptimize-sibling-calls")
    #pragma GCC optimize("-fexpensive-optimizations")
    #pragma GCC optimize("-funsafe-loop-optimizations")
    #pragma GCC optimize("inline-functions-called-once")
    #pragma GCC optimize("-fdelete-null-pointer-checks")
}
using namespace fast;

inline string read_string() {
	char ch = getchar(); string st1 = "";
	while (!((ch >= 'A') && (ch <= 'Z'))) ch = getchar();
	while ((ch >= 'A') && (ch <= 'Z'))  st1 += ch, ch = getchar();
	return st1;
}
char buf[1 << 23], * p1 = buf, * p2 = buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
template<typename T> inline void re(T& x) { x = 0; T f = 1; char ch = getchar();  while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * (1 << 1) + x * (1 << 3) + (ch - 48); ch = getchar(); } x *= f; }
template<typename x, typename... y>void re(x& a, y&... b) { re(a); re(b...); }
template<typename T> inline void ps(T x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9)  ps(x / 10); putchar(x % 10 + '0'); }
template<typename x, typename... y>void ps(x& a, y&... b) { ps(a); putchar(' '); ps(b...); }
#define sp putchar(' ')
#define nl putchar('\n')

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);

	int N; re(N);
	vector<string> s(N + 1);
	L(i, 1, N) s[i] = read_string();
	string longest = "";
	L(i, 1, N) {
		build(s[i]);
		if (longest.size() < s[i].size())
			longest = s[i];
	}
	paint(longest);
	dfs(0);
	ps(ans.size()); nl;
	for (auto& c : ans) putchar(c), nl;
}

Compilation message (stderr)

printer.cpp:80: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
   80 |     #pragma GCC optimization (unroll-loops)
      | 
printer.cpp:79:26: warning: '#pragma GCC optimize' is not a string or number [-Wpragmas]
   79 |     #pragma GCC optimize(Ofast)
      |                          ^~~~~
printer.cpp:81:24: warning: '#pragma GCC option' is not a string [-Wpragmas]
   81 |     #pragma GCC target(avx,avx2,fma)
      |                        ^~~
printer.cpp:82:24: warning: '#pragma GCC option' is not a string [-Wpragmas]
   82 |     #pragma GCC target(sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native)
      |                        ^~~
printer.cpp:102:43: warning: bad option '-fwhole-program' to pragma 'optimize' [-Wpragmas]
  102 |     #pragma GCC optimize("-fwhole-program")
      |                                           ^
printer.cpp:109:45: warning: bad option '-fstrict-overflow' to pragma 'optimize' [-Wpragmas]
  109 |     #pragma GCC optimize("-fstrict-overflow")
      |                                             ^
printer.cpp:111:45: warning: bad option '-fcse-skip-blocks' to pragma 'optimize' [-Wpragmas]
  111 |     #pragma GCC optimize("-fcse-skip-blocks")
      |                                             ^
printer.cpp:125:55: warning: bad option '-funsafe-loop-optimizations' to pragma 'optimize' [-Wpragmas]
  125 |     #pragma GCC optimize("-funsafe-loop-optimizations")
      |                                                       ^
printer.cpp:131:27: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  131 | inline string read_string() {
      |                           ^
printer.cpp:131:27: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
printer.cpp:131:27: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
printer.cpp:131:27: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
printer.cpp:139:41: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  139 | template<typename T> inline void re(T& x) { x = 0; T f = 1; char ch = getchar();  while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); } while (isdigit(ch)) { x = x * (1 << 1) + x * (1 << 3) + (ch - 48); ch = getchar(); } x *= f; }
      |                                         ^
printer.cpp:139:41: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
printer.cpp:139:41: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
printer.cpp:139:41: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
printer.cpp:140:57: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  140 | template<typename x, typename... y>void re(x& a, y&... b) { re(a); re(b...); }
      |                                                         ^
printer.cpp:140:57: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
printer.cpp:140:57: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
printer.cpp:140:57: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
printer.cpp:141:40: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  141 | template<typename T> inline void ps(T x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9)  ps(x / 10); putchar(x % 10 + '0'); }
      |                                        ^
printer.cpp:141:40: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
printer.cpp:141:40: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
printer.cpp:141:40: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
printer.cpp:142:57: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  142 | template<typename x, typename... y>void ps(x& a, y&... b) { ps(a); putchar(' '); ps(b...); }
      |                                                         ^
printer.cpp:142:57: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
printer.cpp:142:57: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
printer.cpp:142:57: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]
printer.cpp:146:10: warning: bad option '-fwhole-program' to attribute 'optimize' [-Wattributes]
  146 | int main() {
      |          ^
printer.cpp:146:10: warning: bad option '-fstrict-overflow' to attribute 'optimize' [-Wattributes]
printer.cpp:146:10: warning: bad option '-fcse-skip-blocks' to attribute 'optimize' [-Wattributes]
printer.cpp:146:10: warning: bad option '-funsafe-loop-optimizations' to attribute 'optimize' [-Wattributes]

• Subtask 1: 0 / 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