Submission #258080

#	Time	Username	Problem	Language	Result	Execution time	Memory
258080		Namnamseo	Swap (BOI16_swap)	C++17	100 / 100	131 ms	30332 KiB

swap

#include <bits/stdc++.h>
using namespace std;
void read(int& x){ scanf("%d",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back
const int inf = 1e9;

int n;
int arr[200010];

struct kumi {
	vector<kumi*> child;
	int val;
	int pick(){
		if(val) return val;
		int ret=inf;
		for(kumi* c : child) ret=min(ret, c->pick());
		return ret;
	}
	
	void poll(int x){
		if(val){
			val = inf;
		} else {
			int n=child.size();
			for(int i=0; i<n; ++i) if(child[i]->pick() == x){
				child[i]->poll(x);
				child.erase(child.begin() + i);
				break;
			}
		}
	}
};

kumi* my[200010];

int main()
{
    read(n);
    for(int i=1; i<=n; ++i) read(arr[i]);
    
    for(int i=1; i<=n; ++i){
		kumi* pt = new kumi();
		pt->val = arr[i];
		kumi* p = new kumi();
		p->val=0; p->child.pb(pt);
		my[i] = p;
    }
    
    for(int i=1; i<=n; ++i){
		int lv=inf, rv=inf;
		if(i*2 <= n) lv=arr[i*2];
		if(i*2+1 <= n) rv=arr[i*2+1];
		assert(my[i]->child.size());
		int mv=my[i]->pick();
		int min_val = min({lv, rv, mv});
		printf("%d ", min_val);
		if(min_val == mv){
			my[i]->poll(mv);
		} else if(min_val == lv){
			my[i*2] = my[i];
		} else {
			my[i*2]->child.pb(my[i]);
			my[i*2+1] = my[i*2];
		}
    }
    return 0;
}

Compilation message (stderr)

swap.cpp: In function 'void read(int&)':
swap.cpp:3:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(int& x){ scanf("%d",&x); }
                    ~~~~~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 27 / 27
• Subtask 4: 20 / 20
• Subtask 5: 32 / 32