oj.uz

Submission #260283

# Submission time Handle Problem Language Result Execution time Memory
260283 2020-08-10T02:55:32 Z arnold518 Swap (BOI16_swap) C++14
0 / 100
 7 ms 9728 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
const int MAXN = 2e5;
 
int N, A[MAXN+10];
vector<int> V[MAXN+10], C[MAXN+10];
 
int dep[MAXN+10];
bool vis[MAXN+10][36];
int dp[MAXN+10][36], memo[MAXN+10][36], ans[MAXN+10];
 
int solve(int now, int pp)
{
	int qq=lower_bound(V[now].begin(), V[now].end(), pp)-V[now].begin();
	if(vis[now][qq]) return dp[now][qq];
	vis[now][qq]=1;
	int &ret=dp[now][qq];
	int &mem=memo[now][qq];
 
	if(now*2>N)
	{
		ret=now;
		return ret;
	}
	if(now*2+1>N)
	{
		if(A[pp]>A[now*2]) ret=now*2;
		else ret=now;
		return ret;
	}
 
	if(A[pp]<A[now*2] && A[pp]<A[now*2+1])
	{
		ret=now;
		return ret;
	}
	if(A[now*2]<A[pp] && A[now*2]<A[now*2+1])
	{
		ret=solve(now*2, pp);
		return ret;
	}
	if(A[now*2+1]<A[pp] && A[now*2+1]<A[now*2])
	{
		int p1=solve(now*2, pp), q1=solve(now*2+1, now*2);
		int p2=solve(now*2, now*2), q2=solve(now*2+1, pp);
		if(A[pp]<A[now*2]) assert(p1<=p2);
		if(A[pp]>A[now*2]) assert(p1>=p2);
		if(A[now*2]<A[pp]) assert(q1<=q2);
		if(A[now*2]>A[pp]) assert(q1>=q2);

		int flag;
		if(min(dep[p1], dep[p2])<=min(dep[q1], dep[q2]))
		{
			if(p1==p2)
			{
				if(A[pp]<A[now*2]) flag=1;
				else flag=2;
			}
			if(p1<p2) flag=1;
			if(p1>p2) flag=2;
		}
		else
		{
			if(q1==q2)
			{
				if(A[now*2]<A[pp]) flag=1;
				else flag=2;
			}
			if(q1<q2) flag=1;
			else flag=2;
		}
		mem=flag;
		if(flag==1) ret=p1;
		else ret=q2;
		return ret;
	}
}

void restore(int now, int pp)
{
	int qq=lower_bound(V[now].begin(), V[now].end(), pp)-V[now].begin();
	solve(now, pp);
	int mem=memo[now][qq];
	if(now*2>N)
	{
 		ans[now]=A[pp];
		return;
	}
	if(now*2+1>N)
	{
		if(A[pp]<A[now*2]) ans[now]=A[pp], ans[now*2]=A[now*2];
		else ans[now]=A[now*2], ans[now*2]=A[pp];
		return;
	}
 
	if(A[pp]<A[now*2] && A[pp]<A[now*2+1])
	{
		ans[now]=A[pp];
		restore(now*2, now*2);
		restore(now*2+1, now*2+1);
		return;
	}
	if(A[now*2]<A[pp] && A[now*2]<A[now*2+1])
	{
		ans[now]=A[now*2];
		restore(now*2, pp);
		restore(now*2+1, now*2+1);
		return;
	}
	if(A[now*2+1]<A[pp] && A[now*2+1]<A[now*2])
	{
		ans[now]=A[now*2+1];
		if(mem==1) { restore(now*2, pp); restore(now*2+1, now*2); }
		else { restore(now*2, now*2); restore(now*2+1, pp); }
	}
}

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++) scanf("%d", &A[i]);
 
	for(int i=1; i<=N; i++)
	{
		int now=i; dep[i]=1;
		while(now!=1)
		{
			dep[i]++;
			V[i].push_back(now);
			C[now].push_back(i);
			if(now%2) V[i].push_back(now-1);
			now/=2;
		}
		C[1].push_back(i);
		V[i].push_back(1);
		reverse(V[i].begin(), V[i].end());
	}
	 
	restore(1, 1);
	for(int i=1; i<=N; i++) printf("%d ", ans[i]);
}

Compilation message

swap.cpp: In function 'int solve(int, int)':
swap.cpp:82:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
swap.cpp: In function 'int main()':
swap.cpp:125:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
swap.cpp:126:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=N; i++) scanf("%d", &A[i]);
                          ~~~~~^~~~~~~~~~~~~
swap.cpp: In function 'int solve(int, int)':
swap.cpp:77:6: warning: 'flag' may be used uninitialized in this function [-Wmaybe-uninitialized]
   mem=flag;
   ~~~^~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 6 ms 9728 KB Output is correct
3 Correct 6 ms 9728 KB Output is correct
4 Incorrect 6 ms 9728 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 6 ms 9728 KB Output is correct
3 Correct 6 ms 9728 KB Output is correct
4 Incorrect 6 ms 9728 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 6 ms 9728 KB Output is correct
3 Correct 6 ms 9728 KB Output is correct
4 Incorrect 6 ms 9728 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 6 ms 9728 KB Output is correct
3 Correct 6 ms 9728 KB Output is correct
4 Incorrect 6 ms 9728 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9728 KB Output is correct
2 Correct 6 ms 9728 KB Output is correct
3 Correct 6 ms 9728 KB Output is correct
4 Incorrect 6 ms 9728 KB Output isn't correct
5 Halted 0 ms 0 KB -