Submission #434353

#	Time	Username	Problem	Language	Result	Execution time	Memory
434353		20160161simone	Comparing Plants (IOI20_plants)	C++14	0 / 100	1 ms	332 KiB

plants

#include"plants.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll N=2e5+10;
ll n,a[N*2];
struct edge{
	ll to,nxt;
};
vector<edge> ln;
ll topln=0,idx[N],d[N];
void add_edge(ll u,ll v){
	ln.push_back((edge){v,idx[u]}),idx[u]=++topln;
	d[v]++;
}
ll vis[N],val[N],vis2[N];
void topo(ll x,ll k){
	vis[x]=1,val[x]=k;
	for(ll i=idx[x];i;i=ln[i].nxt){
		d[ln[i].to]--;
		if(!d[ln[i].to] && !vis[ln[i].to]) topo(ln[i].to,k-1);
	}
}

void init(int k, vector<int> r) {
	n=r.size();
	ln.push_back((edge){0,0});
	for(ll i=1;i<=n;i++) a[i]=a[i+n]=r[i-1];
	for(ll i=n;i>=1;i--){
		for(ll j=1;j<=n;j++){
			if(a[j]) continue;
			ll f=1;
			for(ll t=j+n-1;t>=j+n-k+1;t--)
				if(!a[t] && !vis2[t]){
					f=0;
					break;
				}
			if(f==0) continue;
			vis2[j]=1;
			if(j>n) vis2[j-n]=1;
			else vis2[j+n]=1;
			for(ll t=j+n-1;t>=j+n-k+1;t--){
				if(vis2[t]) continue;
				if(t<=n) add_edge(j,t),a[t+n]--;
				else add_edge(j,t-n),a[t-n]--;
				a[t]--;
			}
			val[j]=i;
			break;
		}
	}
/*	for(ll i=1;i<=n;i++){
		if(vis[i]) continue;
		if(d[i]==0) topo(i,n);
	}
*/
//	for(ll i=1;i<=n;i++) printf("%lld ",val[i]);cout<<endl;
}

int compare_plants(int a, int b) {
	if(val[a+1]>val[b+1]) return 1;
	else return -1;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 14
• Subtask 3: 0 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25