Submission #199047

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
199047	2020-01-28T18:57:53 Z	stefdasca	Swap (BOI16_swap)	C++14	100 / 100	67 ms	5752 KB

swap

#include<bits/stdc++.h>
#define god dimasi5eks
#pragma GCC optimize("O3")
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mod 1000000007
#define dancila 3.14159265359
#define eps 1e-9

// #define fisier 1

using namespace std;

typedef long long ll;

int n, v[400002], t[400002], ans[400002];

int get_value(int poz)
{
    int sol = (1<<30);
    for(; poz; poz >>= 1)
    {
        if(t[poz] != 1)
            sol = min(sol, v[poz]);
        if(t[poz] == 0)
            break;
        if((poz & 1) && t[poz ^ 1] != 0)
        {
            sol = min(sol, v[poz ^ 1]);
            if(t[poz ^ 1] == 1)
                break;
        }
    }
    return sol;
}
void set_value(int poz, int val)
{
    for(; poz; poz >>= 1)
    {
        if(v[poz] == val)
        {
            t[poz] = 0;
            break;
        }
        if(poz & 1)
        {
			if(v[poz ^ 1] == val)
			{
				t[poz] = t[poz ^ 1] = 1;
				break;
			}
            else
                t[poz ^ 1] = 0;
		}
		t[poz] = 1;
    }
}
int main()
{

    #ifdef fisier
        ifstream f("input.in");
        ofstream g("output.out");
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    for(int i = 1; i <= n; ++i)
        cin >> v[i], t[i] = 2;
    t[1] = 0;
    for(int i = n+1; i <= 2*n+1; ++i)
        v[i] = (1<<30);
    for(int i = 1; i <= n; ++i)
    {
        int val = get_value(i);
        ans[i] = min(val, min(v[i << 1], v[i << 1|1]));
        if(ans[i] == val)
        {
            t[i << 1] = t[i << 1|1] = 0;
            set_value(i, ans[i]);
        }
        if(ans[i] == v[i << 1])
            t[i << 1] = 1, t[i << 1|1] = 0;
        if(ans[i] == v[i << 1|1])
            t[i << 1|1] = 1;
    }
    for(int i = 1; i <= n; ++i)
        cout << ans[i] << " ";
    return 0;
}

Subtask #1

10.0 / 10.0

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

Subtask #2

11.0 / 11.0

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

Subtask #3

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	6 ms	504 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	376 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	5 ms	376 KB	Output is correct
10	Correct	5 ms	376 KB	Output is correct
11	Correct	5 ms	376 KB	Output is correct
12	Correct	5 ms	376 KB	Output is correct
13	Correct	5 ms	376 KB	Output is correct
14	Correct	5 ms	380 KB	Output is correct
15	Correct	6 ms	376 KB	Output is correct

Subtask #4

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	6 ms	504 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	376 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	5 ms	376 KB	Output is correct
10	Correct	5 ms	376 KB	Output is correct
11	Correct	5 ms	376 KB	Output is correct
12	Correct	5 ms	376 KB	Output is correct
13	Correct	5 ms	376 KB	Output is correct
14	Correct	5 ms	380 KB	Output is correct
15	Correct	6 ms	376 KB	Output is correct
16	Correct	18 ms	1656 KB	Output is correct
17	Correct	17 ms	1656 KB	Output is correct
18	Correct	17 ms	1656 KB	Output is correct
19	Correct	22 ms	1656 KB	Output is correct
20	Correct	19 ms	1656 KB	Output is correct

Subtask #5

32.0 / 32.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	376 KB	Output is correct
2	Correct	5 ms	376 KB	Output is correct
3	Correct	6 ms	504 KB	Output is correct
4	Correct	5 ms	376 KB	Output is correct
5	Correct	5 ms	376 KB	Output is correct
6	Correct	5 ms	376 KB	Output is correct
7	Correct	5 ms	376 KB	Output is correct
8	Correct	5 ms	376 KB	Output is correct
9	Correct	5 ms	376 KB	Output is correct
10	Correct	5 ms	376 KB	Output is correct
11	Correct	5 ms	376 KB	Output is correct
12	Correct	5 ms	376 KB	Output is correct
13	Correct	5 ms	376 KB	Output is correct
14	Correct	5 ms	380 KB	Output is correct
15	Correct	6 ms	376 KB	Output is correct
16	Correct	18 ms	1656 KB	Output is correct
17	Correct	17 ms	1656 KB	Output is correct
18	Correct	17 ms	1656 KB	Output is correct
19	Correct	22 ms	1656 KB	Output is correct
20	Correct	19 ms	1656 KB	Output is correct
21	Correct	60 ms	5752 KB	Output is correct
22	Correct	54 ms	5496 KB	Output is correct
23	Correct	54 ms	5624 KB	Output is correct
24	Correct	67 ms	5624 KB	Output is correct
25	Correct	66 ms	5496 KB	Output is correct