提出 #6493866


ソースコード 拡げる

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*2];

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 (; K >= 1; K --)
	{
		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();
				}
			}
		}
		cur = 1;
	}
	for (auto x : ret)
		printf("%d ", x);
	
	return 0;
}

提出情報

提出日時
問題 B - Do Not Duplicate
ユーザ liouzhou_101
言語 C++14 (GCC 5.4.1)
得点 700
コード長 3826 Byte
結果 AC
実行時間 425 ms
メモリ 161780 KB

ジャッジ結果

セット名 Sample All
得点 / 配点 0 / 0 700 / 700
結果
AC × 4
AC × 34
セット名 テストケース
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
ケース名 結果 実行時間 メモリ
01-01.txt AC 3 ms 6400 KB
01-02.txt AC 57 ms 42880 KB
01-03.txt AC 66 ms 49024 KB
01-04.txt AC 312 ms 137984 KB
01-05.txt AC 37 ms 30464 KB
01-06.txt AC 293 ms 144256 KB
01-07.txt AC 243 ms 125696 KB
01-08.txt AC 135 ms 89216 KB
01-09.txt AC 268 ms 136832 KB
01-10.txt AC 333 ms 151296 KB
01-11.txt AC 149 ms 89720 KB
01-12.txt AC 104 ms 72192 KB
01-13.txt AC 163 ms 95104 KB
01-14.txt AC 141 ms 94464 KB
01-15.txt AC 284 ms 148352 KB
01-16.txt AC 365 ms 158720 KB
01-17.txt AC 380 ms 158720 KB
01-18.txt AC 367 ms 158720 KB
01-19.txt AC 381 ms 158848 KB
01-20.txt AC 361 ms 158848 KB
01-21.txt AC 362 ms 158848 KB
01-22.txt AC 364 ms 159616 KB
01-23.txt AC 379 ms 159616 KB
01-24.txt AC 402 ms 159616 KB
01-25.txt AC 425 ms 161268 KB
01-26.txt AC 396 ms 161140 KB
01-27.txt AC 411 ms 160632 KB
01-28.txt AC 329 ms 158720 KB
01-29.txt AC 337 ms 158720 KB
01-30.txt AC 394 ms 161780 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