oj.uz

Submission #956585

# Submission time Handle Problem Language Result Execution time Memory
956585 2024-04-02T07:51:02 Z Trisanu_Das Swap (BOI16_swap) C++17
100 / 100
 605 ms 4784 KB 
#include<bits/stdc++.h>
#define T(a,b,c) make_tuple(a,b,c)
using namespace std;
int arr[400100],n;
int dp(int i,int v){
	if(i*2>n)
        return 0;
	int x = arr[2*i];
	if(i*2==n)
        return x<v;
	int y=arr[2*i+1];
	if(v<x&&v<y)
        return 0;
	if(x<v&&x<y)
        return 1 + dp(2*i,v);
	if(v<x)
		return min(dp(2*i,v),dp(2*i+1,v))+1;
	int l1 = dp(2*i,x), l2 = dp(2*i+1,x);
	if(l1<=l2)
        return 1 +dp(2*i+1,v);
	return 1+dp(2*i,v);
}
int main() {
    memset(arr, 7, sizeof arr);
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> arr[i];
    for(int i = 1; i <= n; i++) {
        int &a=arr[i],&b=arr[i*2],&c=arr[i*2+1];
        if(a<b&&a<c);
        else if(b<a&&b<c)
            swap(a,b);
        else {
            swap(a,c);
            if(b>c)
                swap(b,c);
            if(dp(2*i,b)>dp(2*i+1,b)) swap(b,c);
        }
        cout << a << ' ';
    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1888 KB Output is correct
4 Correct 1 ms 1896 KB Output is correct
5 Correct 1 ms 1892 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1888 KB Output is correct
4 Correct 1 ms 1896 KB Output is correct
5 Correct 1 ms 1892 KB Output is correct
6 Correct 1 ms 1888 KB Output is correct
7 Correct 1 ms 1888 KB Output is correct
8 Correct 1 ms 2004 KB Output is correct
9 Correct 1 ms 1884 KB Output is correct
10 Correct 1 ms 2004 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1888 KB Output is correct
4 Correct 1 ms 1896 KB Output is correct
5 Correct 1 ms 1892 KB Output is correct
6 Correct 1 ms 1888 KB Output is correct
7 Correct 1 ms 1888 KB Output is correct
8 Correct 1 ms 2004 KB Output is correct
9 Correct 1 ms 1884 KB Output is correct
10 Correct 1 ms 2004 KB Output is correct
11 Correct 2 ms 1996 KB Output is correct
12 Correct 1 ms 1880 KB Output is correct
13 Correct 1 ms 1884 KB Output is correct
14 Correct 1 ms 1884 KB Output is correct
15 Correct 1 ms 1896 KB Output is correct

Subtask #4
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1888 KB Output is correct
4 Correct 1 ms 1896 KB Output is correct
5 Correct 1 ms 1892 KB Output is correct
6 Correct 1 ms 1888 KB Output is correct
7 Correct 1 ms 1888 KB Output is correct
8 Correct 1 ms 2004 KB Output is correct
9 Correct 1 ms 1884 KB Output is correct
10 Correct 1 ms 2004 KB Output is correct
11 Correct 2 ms 1996 KB Output is correct
12 Correct 1 ms 1880 KB Output is correct
13 Correct 1 ms 1884 KB Output is correct
14 Correct 1 ms 1884 KB Output is correct
15 Correct 1 ms 1896 KB Output is correct
16 Correct 14 ms 2408 KB Output is correct
17 Correct 15 ms 2408 KB Output is correct
18 Correct 14 ms 2356 KB Output is correct
19 Correct 73 ms 2540 KB Output is correct
20 Correct 71 ms 2524 KB Output is correct

Subtask #5
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1884 KB Output is correct
2 Correct 1 ms 1884 KB Output is correct
3 Correct 1 ms 1888 KB Output is correct
4 Correct 1 ms 1896 KB Output is correct
5 Correct 1 ms 1892 KB Output is correct
6 Correct 1 ms 1888 KB Output is correct
7 Correct 1 ms 1888 KB Output is correct
8 Correct 1 ms 2004 KB Output is correct
9 Correct 1 ms 1884 KB Output is correct
10 Correct 1 ms 2004 KB Output is correct
11 Correct 2 ms 1996 KB Output is correct
12 Correct 1 ms 1880 KB Output is correct
13 Correct 1 ms 1884 KB Output is correct
14 Correct 1 ms 1884 KB Output is correct
15 Correct 1 ms 1896 KB Output is correct
16 Correct 14 ms 2408 KB Output is correct
17 Correct 15 ms 2408 KB Output is correct
18 Correct 14 ms 2356 KB Output is correct
19 Correct 73 ms 2540 KB Output is correct
20 Correct 71 ms 2524 KB Output is correct
21 Correct 63 ms 4536 KB Output is correct
22 Correct 59 ms 4548 KB Output is correct
23 Correct 60 ms 4452 KB Output is correct
24 Correct 601 ms 4784 KB Output is correct
25 Correct 605 ms 4432 KB Output is correct