Submission #360214

#	Time	Username	Problem	Language	Result	Execution time	Memory
360214		Kerim	Comparing Plants (IOI20_plants)	C++17	14 / 100	4091 ms	263156 KiB

plants

#include "plants.h"
#include "bits/stdc++.h"
#define MAXN 100009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;

typedef long long ll;
typedef pair<int,int> PII;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int h[MAXN],n,k,s[MAXN<<2],arr[MAXN];
void build(int nd=1,int x=0,int y=n-1){
	for(int i=x;i<=y;i++)s[i]=arr[i];	
}
void inc(int l,int r,int val,int nd=1,int x=0,int y=n-1){
	for(int i=l;i<=r;i++)s[i]+=val;	
}
void upd(int x,int y,int val){
	if(x<=y)
		inc(x,y,val);
	else
		inc(x,n-1,val),inc(0,y,val);
}
int get(){
	for(int i=0;i<n;i++)
		if(!s[i])
			return i;
	return -1;
}	
int vis[MAXN];
vector<int>tmp;
void zero(int i){	
	if(vis[i])return;vis[i]=1;	
	upd(i+1,(i+k-1)%n,1);
}
void flex(int x,int y){
	while(x!=y){
		if(!s[x] and !vis[x])tmp.pb(x);
		x=(x+1)%n;	
	}if(!s[y] and !vis[y])tmp.pb(y);
}
void print(){
	for(int i=0;i<n;i++)printf("%d ",s[i]);puts("");
}
void init(int K, vector<int> r) {
	n=int(r.size());k=K;
	for(int i=0;i<n;i++)arr[i]=r[i];
	build();
	for(int i=0;i<n;i++)
		if(!arr[i])
			zero(i);
	for(int i=n-1;i>=0;i--){
		//print();
		int res=get();
		h[res]=i;
		//debug(res);
		int pre=(res-K+1+n)%n;
		int nex=(res+K-1)%n;
		//cout<<pre<<" "<<nex<<endl;
		upd(res,res,INF);
		upd(pre,res,-1);
		upd(res,nex,-1);
		//print();
		flex(pre,res);flex(res,nex);
		tr(it,tmp)zero(*it);tmp.clear();
	}
}
int compare_plants(int x, int y) {
	int ans=0;
	ans+=(h[x]>h[y]);
	ans-=(h[x]<h[y]);
	return ans;
}

Compilation message (stderr)

plants.cpp: In function 'void zero(int)':
plants.cpp:43:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   43 |  if(vis[i])return;vis[i]=1;
      |  ^~
plants.cpp:43:19: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   43 |  if(vis[i])return;vis[i]=1;
      |                   ^~~
plants.cpp: In function 'void print()':
plants.cpp:53:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   53 |  for(int i=0;i<n;i++)printf("%d ",s[i]);puts("");
      |  ^~~
plants.cpp:53:41: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   53 |  for(int i=0;i<n;i++)printf("%d ",s[i]);puts("");
      |                                         ^~~~
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:10:18: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   10 | #define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
      |                  ^~~
plants.cpp:75:3: note: in expansion of macro 'tr'
   75 |   tr(it,tmp)zero(*it);tmp.clear();
      |   ^~
plants.cpp:75:23: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   75 |   tr(it,tmp)zero(*it);tmp.clear();
      |                       ^~~

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