oj.uz

Submission #360215

# Submission time Handle Problem Language Result Execution time Memory
360215 2021-01-27T20:04:15 Z Kerim Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 263456 KB 
#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])tmp.pb(x);
		x=(x+1)%n;	
	}if(!s[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

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.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 15 ms 512 KB Output is correct
7 Correct 391 ms 3308 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 15 ms 492 KB Output is correct
10 Correct 383 ms 3308 KB Output is correct
11 Correct 267 ms 3436 KB Output is correct
12 Correct 265 ms 3456 KB Output is correct
13 Correct 464 ms 3436 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 15 ms 512 KB Output is correct
7 Correct 391 ms 3308 KB Output is correct
8 Correct 2 ms 364 KB Output is correct
9 Correct 15 ms 492 KB Output is correct
10 Correct 383 ms 3308 KB Output is correct
11 Correct 267 ms 3436 KB Output is correct
12 Correct 265 ms 3456 KB Output is correct
13 Correct 464 ms 3436 KB Output is correct
14 Correct 3411 ms 3724 KB Output is correct
15 Execution timed out 4067 ms 5740 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Execution timed out 4089 ms 263456 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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