oj.uz

답안 #260050

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

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

vector<int> &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<int> &ret=dp[now][qq];

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

	if(A[pp]<A[now*2] && A[pp]<A[now*2+1])
	{
		vector<int> &p=solve(now*2, now*2), &q=solve(now*2+1, now*2+1);
		ret.push_back(A[pp]);
		for(int k=0, i=0, j=0; i<p.size() || j<q.size(); k++)
		{
			for(int t=0; t<(1<<k) && i<p.size(); t++, i++) ret.push_back(p[i]);
			for(int t=0; t<(1<<k) && j<q.size(); t++, j++) ret.push_back(q[j]);
		}
		return ret;
	}
	if(A[now*2]<A[pp] && A[now*2]<A[now*2+1])
	{
		vector<int> &p=solve(now*2, pp), &q=solve(now*2+1, now*2+1);
		ret.push_back(A[now*2]);
		for(int k=0, i=0, j=0; i<p.size() || j<q.size(); k++)
		{
			for(int t=0; t<(1<<k) && i<p.size(); t++, i++) ret.push_back(p[i]);
			for(int t=0; t<(1<<k) && j<q.size(); t++, j++) ret.push_back(q[j]);
		}
		return ret;
	}
	if(A[now*2+1]<A[pp] && A[now*2+1]<A[now*2])
	{
		vector<int> &p1=solve(now*2, pp), &q1=solve(now*2+1, now*2);
		vector<int> &p2=solve(now*2, now*2), &q2=solve(now*2+1, pp);
		ret.push_back(A[now*2+1]);
		int flag=0;
		for(int k=0, i=0, j=0; i<p1.size() || j<q1.size(); k++)
		{
			for(int t=0; t<(1<<k) && i<p1.size(); t++, i++)
			{
				if(flag==1) ret.push_back(p1[i]);
				if(flag==2) ret.push_back(p2[i]);
				if(flag==0)
				{
					if(p1[i]==p2[i]) ret.push_back(p1[i]), flag=0;
					if(p1[i]<p2[i]) ret.push_back(p1[i]), flag=1;
					if(p1[i]>p2[i]) ret.push_back(p2[i]), flag=2;
				}
			}
			for(int t=0; t<(1<<k) && j<q1.size(); t++, j++)
			{
				if(flag==1) ret.push_back(q1[j]);
				if(flag==2) ret.push_back(q2[j]);
				if(flag==0)
				{
					if(q1[j]==q2[j]) ret.push_back(q1[j]), flag=0;
					if(q1[j]<q2[j]) ret.push_back(q1[j]), flag=1;
					if(q1[j]>q2[j]) ret.push_back(q2[j]), flag=2;
				}
			}
		}
		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());
		vis[i].resize(V[i].size());
		dp[i].resize(V[i].size());
	}

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

Compilation message

swap.cpp: In function 'std::vector<int>& solve(int, int)':
swap.cpp:48:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0, i=0, j=0; i<p.size() || j<q.size(); k++)
                          ~^~~~~~~~~
swap.cpp:48:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0, i=0, j=0; i<p.size() || j<q.size(); k++)
                                        ~^~~~~~~~~
swap.cpp:50:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int t=0; t<(1<<k) && i<p.size(); t++, i++) ret.push_back(p[i]);
                             ~^~~~~~~~~
swap.cpp:51:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int t=0; t<(1<<k) && j<q.size(); t++, j++) ret.push_back(q[j]);
                             ~^~~~~~~~~
swap.cpp:59:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0, i=0, j=0; i<p.size() || j<q.size(); k++)
                          ~^~~~~~~~~
swap.cpp:59:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0, i=0, j=0; i<p.size() || j<q.size(); k++)
                                        ~^~~~~~~~~
swap.cpp:61:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int t=0; t<(1<<k) && i<p.size(); t++, i++) ret.push_back(p[i]);
                             ~^~~~~~~~~
swap.cpp:62:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int t=0; t<(1<<k) && j<q.size(); t++, j++) ret.push_back(q[j]);
                             ~^~~~~~~~~
swap.cpp:72:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0, i=0, j=0; i<p1.size() || j<q1.size(); k++)
                          ~^~~~~~~~~~
swap.cpp:72:42: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int k=0, i=0, j=0; i<p1.size() || j<q1.size(); k++)
                                         ~^~~~~~~~~~
swap.cpp:74:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int t=0; t<(1<<k) && i<p1.size(); t++, i++)
                             ~^~~~~~~~~~
swap.cpp:85:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int t=0; t<(1<<k) && j<q1.size(); t++, j++)
                             ~^~~~~~~~~~
swap.cpp:99:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
swap.cpp: In function 'int main()':
swap.cpp:103:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
swap.cpp:104: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 11 ms 17536 KB Output is correct
2 Correct 11 ms 17536 KB Output is correct
3 Correct 11 ms 17536 KB Output is correct
4 Correct 11 ms 17536 KB Output is correct
5 Correct 12 ms 17536 KB Output is correct

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 17536 KB Output is correct
2 Correct 11 ms 17536 KB Output is correct
3 Correct 11 ms 17536 KB Output is correct
4 Correct 11 ms 17536 KB Output is correct
5 Correct 12 ms 17536 KB Output is correct
6 Correct 13 ms 17536 KB Output is correct
7 Correct 12 ms 17536 KB Output is correct
8 Correct 11 ms 17536 KB Output is correct
9 Correct 11 ms 17536 KB Output is correct
10 Correct 13 ms 17536 KB Output is correct

Subtask #3
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 17536 KB Output is correct
2 Correct 11 ms 17536 KB Output is correct
3 Correct 11 ms 17536 KB Output is correct
4 Correct 11 ms 17536 KB Output is correct
5 Correct 12 ms 17536 KB Output is correct
6 Correct 13 ms 17536 KB Output is correct
7 Correct 12 ms 17536 KB Output is correct
8 Correct 11 ms 17536 KB Output is correct
9 Correct 11 ms 17536 KB Output is correct
10 Correct 13 ms 17536 KB Output is correct
11 Correct 13 ms 18048 KB Output is correct
12 Correct 13 ms 18176 KB Output is correct
13 Correct 13 ms 18048 KB Output is correct
14 Correct 14 ms 18304 KB Output is correct
15 Correct 14 ms 18304 KB Output is correct

Subtask #4
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 17536 KB Output is correct
2 Correct 11 ms 17536 KB Output is correct
3 Correct 11 ms 17536 KB Output is correct
4 Correct 11 ms 17536 KB Output is correct
5 Correct 12 ms 17536 KB Output is correct
6 Correct 13 ms 17536 KB Output is correct
7 Correct 12 ms 17536 KB Output is correct
8 Correct 11 ms 17536 KB Output is correct
9 Correct 11 ms 17536 KB Output is correct
10 Correct 13 ms 17536 KB Output is correct
11 Correct 13 ms 18048 KB Output is correct
12 Correct 13 ms 18176 KB Output is correct
13 Correct 13 ms 18048 KB Output is correct
14 Correct 14 ms 18304 KB Output is correct
15 Correct 14 ms 18304 KB Output is correct
16 Correct 143 ms 60740 KB Output is correct
17 Correct 142 ms 60404 KB Output is correct
18 Correct 149 ms 60664 KB Output is correct
19 Correct 367 ms 92000 KB Output is correct
20 Correct 350 ms 91508 KB Output is correct

Subtask #5
0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 17536 KB Output is correct
2 Correct 11 ms 17536 KB Output is correct
3 Correct 11 ms 17536 KB Output is correct
4 Correct 11 ms 17536 KB Output is correct
5 Correct 12 ms 17536 KB Output is correct
6 Correct 13 ms 17536 KB Output is correct
7 Correct 12 ms 17536 KB Output is correct
8 Correct 11 ms 17536 KB Output is correct
9 Correct 11 ms 17536 KB Output is correct
10 Correct 13 ms 17536 KB Output is correct
11 Correct 13 ms 18048 KB Output is correct
12 Correct 13 ms 18176 KB Output is correct
13 Correct 13 ms 18048 KB Output is correct
14 Correct 14 ms 18304 KB Output is correct
15 Correct 14 ms 18304 KB Output is correct
16 Correct 143 ms 60740 KB Output is correct
17 Correct 142 ms 60404 KB Output is correct
18 Correct 149 ms 60664 KB Output is correct
19 Correct 367 ms 92000 KB Output is correct
20 Correct 350 ms 91508 KB Output is correct
21 Correct 583 ms 208620 KB Output is correct
22 Correct 591 ms 208876 KB Output is correct
23 Correct 579 ms 209516 KB Output is correct
24 Runtime error 681 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
25 Halted 0 ms 0 KB -