oj.uz

답안 #199047

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
199047 2020-01-28T18:57:53 Z stefdasca Swap (BOI16_swap) C++14
100 / 100
 67 ms 5752 KB 
#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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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