oj.uz

Submission #27067

# Submission time Handle Problem Language Result Execution time Memory
27067 2017-07-09T06:54:25 Z 서규호(#1119) Swap (BOI16_swap) C++14
0 / 100
 3 ms 8468 KB 
#include <bits/stdc++.h>

#define lld long long
#define pii pair<int,int>
#define pb push_back
#define next nextt
#define Inf 1000000000
#define Linf 1000000000000000000LL
#define Mod 1000000007

using namespace std;

int N;
int a[200002],ans[200002];
bool check[200002];
set<int> q;
vector<int> tmp[200002];

int main(){
    //freopen("input.txt","r",stdin);
	scanf("%d",&N);
	for(int i=1; i<=N; i++){
		scanf("%d",&a[i]);
	}
    for(int i=1; i<=(N-1)/2; i++){
        int t;
        if(a[i] != 0){
            ans[i] = min(a[i],min(a[i*2],a[i*2+1]));
        }else{
            sort(tmp[i].begin(),tmp[i].end());
            for(auto &j : tmp[i]){
                if(!check[j]){
                    t = j;
                    break;
                }
            }
            ans[i] = min(t,min(a[i*2],a[i*2+1]));
        }
        check[ans[i]] = true;
        if(a[i*2] == ans[i]){
            for(auto &j : tmp[i]) tmp[i*2].pb(j);
            if(a[i] != 0) tmp[i*2].pb(a[i]);
            a[i*2] = 0;
        }else if(a[i*2+1] == ans[i]){
            if(a[i] != 0) tmp[i].pb(a[i]);
            tmp[i].pb(a[i*2]);
            for(auto &j : tmp[i]) tmp[i*2].pb(j);
            for(auto &j : tmp[i]) tmp[i*2+1].pb(j);
            a[i*2] = a[i*2+1] = 0;
        }
    }
    if(N%2 == 0){
        if(a[N/2] != 0){
            ans[N/2] = min(a[N/2],a[N]);
            if(ans[N/2] == a[N]) a[N] = a[N/2];
        }else{
            sort(tmp[N/2].begin(),tmp[N/2].end());
            for(auto &j : tmp[N/2]){
                if(!check[j]){
                    ans[N/2] = min(j,a[N]);
                    if(ans[N/2] == a[N]){
                        for(auto &k : tmp[N/2]) tmp[N].pb(k);
                    }
                    break;
                }
            }
        }
        check[ans[N/2]] = true;
    }
    for(int i=N/2+1; i<=N; i++){
        if(a[i] != 0) ans[i] = a[i];
        else{
            sort(tmp[i].begin(),tmp[i].end());
            for(auto &j : tmp[i]){
                if(!check[j]){
                    ans[i] = j;
                    break;
                }
            }
        }
        check[ans[i]] = true;
    }
	for(int i=1; i<=N; i++) printf("%d ",ans[i]);

	return 0;
}

Compilation message

swap.cpp: In function 'int main()':
swap.cpp:21:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
                ^
swap.cpp:23:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
                    ^
swap.cpp:26:13: warning: 't' may be used uninitialized in this function [-Wmaybe-uninitialized]
         int t;
             ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8468 KB Output is correct
2 Incorrect 3 ms 8468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8468 KB Output is correct
2 Incorrect 3 ms 8468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8468 KB Output is correct
2 Incorrect 3 ms 8468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8468 KB Output is correct
2 Incorrect 3 ms 8468 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8468 KB Output is correct
2 Incorrect 3 ms 8468 KB Output isn't correct
3 Halted 0 ms 0 KB -