Submission #52398116

---

Source Code Expand

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;

int n;
int a[200010];
int fa[30][400010];
int to[200010],nxt[200010],head[200010],cnt;
int p[200010],b[200010];

void add(int x,int y)
{
	if (x < y) swap(x,y);
	to[++ cnt] = y;
	nxt[cnt] = head[x];
	head[x] = cnt;
}

int fnd(int x,int k) {return fa[k][x] = (fa[k][x] == x ? x : fnd(fa[k][x],k));}

void Merge(int l,int r,int k)
{
	// printf("*Merge %d %d %d\n",l,r,k);
	l = fnd(l,k),r = fnd(r,k);
	if (l == r) return ;
	if (l < r) swap(l,r);
	fa[k][l] = r;
}

void merge(int l,int ll,int len)
{
	// printf("merge %d %d %d\n",l,ll,len);
	if (l == ll) return ;
	int r = l + len - 1,rr = ll + len - 1;
	int L = (len == 1 ? 0 : log2(len));
	Merge(l,ll,L);
	Merge(r - (1 << L) + 1,rr - (1 << L) + 1,L);
}

int main()
{
	scanf("%d",&n);
	for (int i = 1;i <= 2 * n;i ++)
		for (int j = 0;j <= 20;j ++)
			fa[j][i] = i;
	for (int i = n + 1;i <= n * 2;i ++) Merge(2 * n - i + 1,i,0);
	for (int i = 1;i <= n;i ++)
	{
		scanf("%d",a + i);
		if (!a[i]) continue;
		merge(i - a[i],2 * n - (i + a[i]) + 1,a[i]);
		merge(i + 1,2 * n - i + 2,a[i]);
	}
	for (int i = 19;~i;i --)
		for (int j = 1;j <= 2 * n - (1 << (i + 1)) + 1;j ++)
		{
			int tmp = fnd(j,i + 1);
			Merge(j,tmp,i);
			Merge(j + (1 << i),tmp + (1 << i),i);
		}
	// for (int i = 1;i <= n;i ++) printf("%d %d\n",i,fnd(i,0));
	for (int i = 1;i <= n;i ++)
	{
		if (a[i] == i - 1 || a[i] == n - i) continue;
		if (fnd(i - a[i] - 1,0) == fnd(i + a[i] + 1,0))
		{
			printf("No\n");
			return 0;
		}
		add(fnd(i - a[i] - 1,0),fnd(i + a[i] + 1,0));
	}
	printf("Yes\n");
	for (int i = 1;i <= n;i ++)
		if (i == fnd(i,0))
		{
			int nw = 1;
			for (int j = head[i];j;j = nxt[j])
				p[b[to[j]]] = 1;//printf("*%d %d %d\n",i,j,b[j]);
			while (p[nw]) nw ++;
			b[i] = nw;
			printf("%d ",nw);
			for (int j = head[i];j;j = nxt[j]) p[b[to[j]]] = 0;
		}
		else printf("%d ",b[fnd(i,0)]);
	printf("\n");
}

Submission Info

Compile Error

Main.cpp: In function ‘int main()’:
Main.cpp:43:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   43 |         scanf("%d",&n);
      |         ~~~~~^~~~~~~~~
Main.cpp:50:22: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   50 |                 scanf("%d",a + i);
      |                 ~~~~~^~~~~~~~~~~~

Judge Result