oj.uz

Submission #64553

# Submission time Handle Problem Language Result Execution time Memory
64553 2018-08-04T20:56:02 Z zetapi Swap (BOI16_swap) C++14
100 / 100
 307 ms 25596 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define pb  push_back
#define mp  make_pair
#define int long long
#define itr ::iterator 
 
typedef pair<int,int>  pii;
 
const int MAX=1e6;
 
int N,n,arr[MAX],p[MAX];
 
map<pii,int> dp;
map<pii,int> bes;

int get(int ind, int y) {
    if (bes.count({ind,y})) return bes[{ind,y}];
    if (2*ind > n) return ind;
    if (2*ind+1 > n) {
        if (y > p[2*ind]) return 2*ind;
        return ind;
    }
    
    if (y < min(p[2*ind],p[2*ind+1])) return bes[{ind,y}] = ind;
    if (p[2*ind] < min(y,p[2*ind+1])) return bes[{ind,y}] = get(2*ind,y);
    
    int mn = min(y,p[2*ind]);
    if (get(2*ind,mn) < get(2*ind+1,mn)) {
        if (mn == y) return bes[{ind,y}] = get(2*ind,y);
        return bes[{ind,y}] = get(2*ind+1,y);
    } else {
        if (mn == y) return bes[{ind,y}] = get(2*ind+1,y);
        return bes[{ind,y}] = get(2*ind,y);
    }
}

int get1(int X,int val)	//get the minimum index possible
{
	if(dp.count(mp(X,val)))
		return dp[mp(X,val)];
	else if(2*X>N)
		return dp[mp(X,val)]=X;
	else if(2*X+1>N)
	{
		if(arr[2*X]<val)
			return dp[mp(X,val)]=2*X;
		else
			return dp[mp(X,val)]=X;
	}
	else if(val<arr[2*X] and val<arr[2*X+1])
		return dp[mp(X,val)]=X;
	else if(arr[2*X+1]<val)
	{
		if(arr[2*X]<arr[2*X+1])
			return dp[mp(X,val)]=get1(2*X,val);
		else
			return min(get(2*X,val),get1(2*X+1,val));
	}
	else if(arr[2*X]<val)
		return dp[mp(X,val)]=get1(2*X,val);
}
 
void solve(int X)
{
	if(2*X>N)
		return ;
	else if(2*X+1>N)
	{
		if(arr[2*X]<arr[X])
			swap(arr[2*X],arr[X]);
		return ;
	}
	else if(arr[2*X+1]<arr[X])
	{
		if(arr[2*X]<arr[2*X+1])
		{
			swap(arr[X],arr[2*X]);
			return ;
		}
		swap(arr[X],arr[2*X+1]);
		int mn=min(arr[2*X],arr[2*X+1]);
		int mx=max(arr[2*X],arr[2*X+1]);
		if(get(2*X,mn)<get(2*X+1,mn))
		{
			arr[2*X]=mn;
			arr[2*X+1]=mx;
		}
		else
		{
			arr[2*X]=mx;
			arr[2*X+1]=mn;
		}
		//cout<<2*X<<" "<<mn<<" "<<get(2*X,mn)<<"\n";
		//cout<<2*X+1<<" "<<mn<<" "<<get(2*X+1,mn)<<"\n";
		return ;
	}
	else if(arr[2*X]<arr[X])
		swap(arr[X],arr[2*X]);
	return ;
}
 
signed main()
{
	ios_base::sync_with_stdio(false);
 
	cin>>N;
	n=N;
	for(int A=1;A<=N;A++)
	{
		cin>>arr[A];
		p[A]=arr[A];
	}
	for(int A=1;A<=N;A++)
		solve(A);	
	for(int A=1;A<=N;A++)
		cout<<arr[A]<<" ";
	return 0;
}

Compilation message

swap.cpp: In function 'long long int get1(long long int, long long int)':
swap.cpp:63:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 624 KB Output is correct
4 Correct 2 ms 624 KB Output is correct
5 Correct 3 ms 624 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 624 KB Output is correct
4 Correct 2 ms 624 KB Output is correct
5 Correct 3 ms 624 KB Output is correct
6 Correct 3 ms 732 KB Output is correct
7 Correct 2 ms 780 KB Output is correct
8 Correct 2 ms 780 KB Output is correct
9 Correct 2 ms 780 KB Output is correct
10 Correct 2 ms 780 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 624 KB Output is correct
4 Correct 2 ms 624 KB Output is correct
5 Correct 3 ms 624 KB Output is correct
6 Correct 3 ms 732 KB Output is correct
7 Correct 2 ms 780 KB Output is correct
8 Correct 2 ms 780 KB Output is correct
9 Correct 2 ms 780 KB Output is correct
10 Correct 2 ms 780 KB Output is correct
11 Correct 4 ms 780 KB Output is correct
12 Correct 4 ms 784 KB Output is correct
13 Correct 1 ms 784 KB Output is correct
14 Correct 4 ms 916 KB Output is correct
15 Correct 4 ms 916 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 624 KB Output is correct
4 Correct 2 ms 624 KB Output is correct
5 Correct 3 ms 624 KB Output is correct
6 Correct 3 ms 732 KB Output is correct
7 Correct 2 ms 780 KB Output is correct
8 Correct 2 ms 780 KB Output is correct
9 Correct 2 ms 780 KB Output is correct
10 Correct 2 ms 780 KB Output is correct
11 Correct 4 ms 780 KB Output is correct
12 Correct 4 ms 784 KB Output is correct
13 Correct 1 ms 784 KB Output is correct
14 Correct 4 ms 916 KB Output is correct
15 Correct 4 ms 916 KB Output is correct
16 Correct 34 ms 3392 KB Output is correct
17 Correct 36 ms 3684 KB Output is correct
18 Correct 32 ms 3920 KB Output is correct
19 Correct 71 ms 6140 KB Output is correct
20 Correct 65 ms 6552 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 624 KB Output is correct
4 Correct 2 ms 624 KB Output is correct
5 Correct 3 ms 624 KB Output is correct
6 Correct 3 ms 732 KB Output is correct
7 Correct 2 ms 780 KB Output is correct
8 Correct 2 ms 780 KB Output is correct
9 Correct 2 ms 780 KB Output is correct
10 Correct 2 ms 780 KB Output is correct
11 Correct 4 ms 780 KB Output is correct
12 Correct 4 ms 784 KB Output is correct
13 Correct 1 ms 784 KB Output is correct
14 Correct 4 ms 916 KB Output is correct
15 Correct 4 ms 916 KB Output is correct
16 Correct 34 ms 3392 KB Output is correct
17 Correct 36 ms 3684 KB Output is correct
18 Correct 32 ms 3920 KB Output is correct
19 Correct 71 ms 6140 KB Output is correct
20 Correct 65 ms 6552 KB Output is correct
21 Correct 118 ms 12704 KB Output is correct
22 Correct 136 ms 13924 KB Output is correct
23 Correct 116 ms 15156 KB Output is correct
24 Correct 307 ms 24324 KB Output is correct
25 Correct 295 ms 25596 KB Output is correct