oj.uz

답안 #260043

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
260043 2020-08-09T06:14:17 Z arnold518 Swap (BOI16_swap) C++14
48 / 100
 210 ms 262148 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];

bool vis[MAXN+10][50];
vector<pii> dp[MAXN+10][50];

vector<pii> &solve(int now, int pp)
{
	int qq=lower_bound(V[now].begin(), V[now].end(), pp)-V[now].begin();
	if(V[now][qq]!=pp) while(1);
	if(vis[now][qq]) return dp[now][qq];
	vis[now][qq]=1;
	vector<pii> &ret=dp[now][qq];

	if(now*2>N)
	{
		ret.push_back({now, A[pp]});
		return ret;
	}
	if(now*2+1>N)
	{
		if(A[pp]>A[now*2])
		{
			ret.push_back({now, A[now*2]});
			ret.push_back({now*2, A[pp]});
		}
		else
		{
			ret.push_back({now, A[pp]});
			ret.push_back({now*2, A[now*2]});
		}
		return ret;
	}

	if(A[pp]<A[now*2] && A[pp]<A[now*2+1])
	{
		vector<pii> &p=solve(now*2, now*2), &q=solve(now*2+1, now*2+1);
		ret.resize(p.size()+q.size()+1);
		ret[0]={now, A[pp]};
		merge(p.begin(), p.end(), q.begin(), q.end(), ret.begin()+1);
		return ret;
	}
	if(A[now*2]<A[pp] && A[now*2]<A[now*2+1])
	{
		vector<pii> &p=solve(now*2, pp), &q=solve(now*2+1, now*2+1);
		ret.resize(p.size()+q.size()+1);
		ret[0]={now, A[now*2]};
		merge(p.begin(), p.end(), q.begin(), q.end(), ret.begin()+1);
		return ret;
	}
	if(A[now*2+1]<A[pp] && A[now*2+1]<A[now*2])
	{
		vector<pii> ret1, ret2;
		vector<pii> &p1=solve(now*2, pp), &q1=solve(now*2+1, now*2);
		ret1.resize(p1.size()+q1.size()+1);
		ret1[0]={now, A[now*2+1]};
		merge(p1.begin(), p1.end(), q1.begin(), q1.end(), ret1.begin()+1);

		vector<pii> &p2=solve(now*2, now*2), &q2=solve(now*2+1, pp);
		ret2.resize(p2.size()+q2.size()+1);
		ret2[0]={now, A[now*2+1]};
		merge(p2.begin(), p2.end(), q2.begin(), q2.end(), ret2.begin()+1);
		ret=min(ret1, ret2);
		return ret;
	}
}

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;
		while(now!=1)
		{
			V[i].push_back(now);
			if(now%2) V[i].push_back(now-1);
			now/=2;
		}
		V[i].push_back(1);
		reverse(V[i].begin(), V[i].end());
	}

	vector<pii> ans=solve(1, 1);
	for(auto it : ans) printf("%d ", it.second);
}

Compilation message

swap.cpp: In function 'std::vector<std::pair<int, int> >& solve(int, int)':
swap.cpp:75:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
swap.cpp: In function 'int main()':
swap.cpp:79:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
swap.cpp:80: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]);
                          ~~~~~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 239864 KB Output is correct
2 Correct 170 ms 239864 KB Output is correct
3 Correct 168 ms 239864 KB Output is correct
4 Correct 146 ms 239864 KB Output is correct
5 Correct 171 ms 239864 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 239864 KB Output is correct
2 Correct 170 ms 239864 KB Output is correct
3 Correct 168 ms 239864 KB Output is correct
4 Correct 146 ms 239864 KB Output is correct
5 Correct 171 ms 239864 KB Output is correct
6 Correct 155 ms 239864 KB Output is correct
7 Correct 162 ms 239992 KB Output is correct
8 Correct 169 ms 239808 KB Output is correct
9 Correct 170 ms 239864 KB Output is correct
10 Correct 157 ms 239992 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 239864 KB Output is correct
2 Correct 170 ms 239864 KB Output is correct
3 Correct 168 ms 239864 KB Output is correct
4 Correct 146 ms 239864 KB Output is correct
5 Correct 171 ms 239864 KB Output is correct
6 Correct 155 ms 239864 KB Output is correct
7 Correct 162 ms 239992 KB Output is correct
8 Correct 169 ms 239808 KB Output is correct
9 Correct 170 ms 239864 KB Output is correct
10 Correct 157 ms 239992 KB Output is correct
11 Correct 170 ms 240120 KB Output is correct
12 Correct 173 ms 240252 KB Output is correct
13 Correct 153 ms 240248 KB Output is correct
14 Correct 150 ms 240504 KB Output is correct
15 Correct 150 ms 240504 KB Output is correct

Subtask #4
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 239864 KB Output is correct
2 Correct 170 ms 239864 KB Output is correct
3 Correct 168 ms 239864 KB Output is correct
4 Correct 146 ms 239864 KB Output is correct
5 Correct 171 ms 239864 KB Output is correct
6 Correct 155 ms 239864 KB Output is correct
7 Correct 162 ms 239992 KB Output is correct
8 Correct 169 ms 239808 KB Output is correct
9 Correct 170 ms 239864 KB Output is correct
10 Correct 157 ms 239992 KB Output is correct
11 Correct 170 ms 240120 KB Output is correct
12 Correct 173 ms 240252 KB Output is correct
13 Correct 153 ms 240248 KB Output is correct
14 Correct 150 ms 240504 KB Output is correct
15 Correct 150 ms 240504 KB Output is correct
16 Runtime error 210 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 145 ms 239864 KB Output is correct
2 Correct 170 ms 239864 KB Output is correct
3 Correct 168 ms 239864 KB Output is correct
4 Correct 146 ms 239864 KB Output is correct
5 Correct 171 ms 239864 KB Output is correct
6 Correct 155 ms 239864 KB Output is correct
7 Correct 162 ms 239992 KB Output is correct
8 Correct 169 ms 239808 KB Output is correct
9 Correct 170 ms 239864 KB Output is correct
10 Correct 157 ms 239992 KB Output is correct
11 Correct 170 ms 240120 KB Output is correct
12 Correct 173 ms 240252 KB Output is correct
13 Correct 153 ms 240248 KB Output is correct
14 Correct 150 ms 240504 KB Output is correct
15 Correct 150 ms 240504 KB Output is correct
16 Runtime error 210 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -