Submission #6493540


Source Code Expand

Copy
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma comment(linker, "/stack:200000000")

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;

#define X first
#define Y second

//#include <boost/unordered_map.hpp>
//using namespace boost;

/*
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
rbtree T;
*/

using i32 = int;
using i64 = long long;
using u8 = unsigned char;
using u32 = unsigned;
using u64 = unsigned long long;
using f64 = double;
using f80 = long double;
//using i128 = __int128_t;
//using u128 = __uint128_t;
using i128 = i64;
using u128 = u64;

ll power(ll a, ll b, ll p)
{
	if (!b) return 1;
	ll t = power(a, b/2, p);
	t = t*t%p;
	if (b&1) t = t*a%p;
	return t;
}

ll exgcd(ll a, ll b, ll &x, ll &y)
{
	if (b == 0)
	{
		x = 1;
		y = 0;
		return a;
	}
	ll px, py;
	ll d = exgcd(b, a%b, px, py);
	x = py;
	y = px-a/b*py;
	return d;
}

template<class T>
inline void freshmin(T &a, const T &b)
{
	if (a > b) a = b;
}

template<class T>
inline void freshmax(T &a, const T &b)
{
	if (a < b) a = b;
}

//#define getchar getchar_unlocked
//#define putchar putchar_unlocked

int inp() {
	int x = 0, f = 0; char ch;
	for(ch = getchar(); !isdigit(ch); ch = getchar())
		if(ch == '-') f = 1;
	for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
	return f ? -x : x;
}

ll inp_ll() {
	ll x = 0; int f = 0; char ch;
	for(ch = getchar(); !isdigit(ch); ch = getchar())
		if(ch == '-') f = 1;
	for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
	return f ? -x : x;
}

template<class T>
bool read(T &x)
{
	x = 0;
	char ch = getchar();
	if (ch == EOF) return 0;
	for(; !isdigit(ch); )
	{
		ch = getchar();
		if (ch == EOF) return 0;
	}
	for(; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
	return 1;
}

template<class T>
void write(T x)
{
	static char s[22];
	static char *it = s+20;
	static char *end = s+20;
	if (!x)
		*-- it = '0';
	while (x)
	{
		*-- it = x%10+'0';
		x /= 10;
	}
	for (; it < end; ++ it)
		putchar(*it);
}

template<class T>
void writeln(T x)
{
	write(x);
	putchar('\n');
}

const int MOD = 998244353;
const int INF = 1000000000;
const int MAXN = 200010;
const int MAXK = 66;

int n;
ll K;
int a[MAXN*2], u[MAXN], to[MAXN];

int f[MAXN][MAXK];
ll g[MAXN][MAXK];

int in[MAXN];

int main()
{
	
	n = inp();
	K = inp_ll();
	for (int i = 1; i <= n; ++ i)
		a[i] = a[i+n] = inp();
	for (int i = n+n; i >= 1; -- i)
	{
		to[i] = u[a[i]];
		u[a[i]] = i;
	}
	for (int i = n; i >= 1; -- i)
	{
		if (to[i] == n+n)
		{
			f[i][0] = 1;
			g[i][0] = 2;
		}
		else if (to[i] >= n)
		{
			f[i][0] = to[i]-n+1;
			g[i][0] = 1;
		}
		else
		{
			f[i][0] = to[i]+1;
			g[i][0] = 0;
		}
	}
	for (int k = 1; k <= 60; ++ k)
		for (int i = 1; i <= n; ++ i)
		{
			f[i][k] = f[f[i][k-1]][k-1];
			g[i][k] = g[i][k-1]+g[f[i][k-1]][k-1];
		}
	int cur = 1;
	for (int k = 60; k >= 0; -- k)
		if (K > g[cur][k])
		{
			K -= g[cur][k];
			cur = f[cur][k];
		}
	
	vector<int> ret;
	for (int i = cur; i <= n; ++ i)
	{
		if (!in[a[i]])
		{
			ret.push_back(a[i]);
			in[a[i]] = 1;
		}
		else
		{
			while (in[a[i]])
			{
				in[ret.back()] = 0;
				ret.pop_back();
			}
		}
	}
	for (auto x : ret)
		printf("%d ", x);
	
	return 0;
}

Submission Info

Submission Time
Task B - Do Not Duplicate
User liouzhou_101
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3762 Byte
Status WA
Exec Time 351 ms
Memory 161012 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 700
Status
AC × 4
AC × 15
WA × 19
Set Name Test Cases
Sample sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt
All 01-01.txt, 01-02.txt, 01-03.txt, 01-04.txt, 01-05.txt, 01-06.txt, 01-07.txt, 01-08.txt, 01-09.txt, 01-10.txt, 01-11.txt, 01-12.txt, 01-13.txt, 01-14.txt, 01-15.txt, 01-16.txt, 01-17.txt, 01-18.txt, 01-19.txt, 01-20.txt, 01-21.txt, 01-22.txt, 01-23.txt, 01-24.txt, 01-25.txt, 01-26.txt, 01-27.txt, 01-28.txt, 01-29.txt, 01-30.txt, sample-01.txt, sample-02.txt, sample-03.txt, sample-04.txt
Case Name Status Exec Time Memory
01-01.txt AC 2 ms 6400 KB
01-02.txt AC 55 ms 42496 KB
01-03.txt AC 64 ms 48640 KB
01-04.txt AC 265 ms 137344 KB
01-05.txt AC 31 ms 30208 KB
01-06.txt WA 285 ms 143616 KB
01-07.txt WA 227 ms 125056 KB
01-08.txt WA 133 ms 88448 KB
01-09.txt WA 266 ms 136064 KB
01-10.txt WA 307 ms 150528 KB
01-11.txt WA 149 ms 88952 KB
01-12.txt AC 98 ms 71680 KB
01-13.txt WA 171 ms 95480 KB
01-14.txt AC 150 ms 93824 KB
01-15.txt AC 293 ms 147712 KB
01-16.txt WA 324 ms 158080 KB
01-17.txt WA 350 ms 158080 KB
01-18.txt WA 350 ms 158080 KB
01-19.txt WA 334 ms 158208 KB
01-20.txt WA 348 ms 158208 KB
01-21.txt WA 351 ms 158208 KB
01-22.txt WA 328 ms 158848 KB
01-23.txt WA 330 ms 158848 KB
01-24.txt WA 329 ms 158848 KB
01-25.txt WA 346 ms 161012 KB
01-26.txt WA 329 ms 161012 KB
01-27.txt WA 348 ms 161012 KB
01-28.txt AC 333 ms 158080 KB
01-29.txt AC 313 ms 158080 KB
01-30.txt AC 347 ms 161012 KB
sample-01.txt AC 2 ms 6400 KB
sample-02.txt AC 2 ms 6400 KB
sample-03.txt AC 2 ms 6400 KB
sample-04.txt AC 2 ms 6400 KB