oj.uz

Submission #360214

# Submission time Handle Problem Language Result Execution time Memory
360214 2021-01-27T19:55:06 Z Kerim Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 263156 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] 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

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 1 ms 364 KB Output is correct
2 Correct 1 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 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 15 ms 364 KB Output is correct
7 Correct 390 ms 5356 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 16 ms 492 KB Output is correct
10 Correct 389 ms 5356 KB Output is correct
11 Correct 270 ms 5260 KB Output is correct
12 Correct 273 ms 5356 KB Output is correct
13 Correct 468 ms 5356 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 15 ms 364 KB Output is correct
7 Correct 390 ms 5356 KB Output is correct
8 Correct 3 ms 492 KB Output is correct
9 Correct 16 ms 492 KB Output is correct
10 Correct 389 ms 5356 KB Output is correct
11 Correct 270 ms 5260 KB Output is correct
12 Correct 273 ms 5356 KB Output is correct
13 Correct 468 ms 5356 KB Output is correct
14 Correct 3492 ms 5948 KB Output is correct
15 Execution timed out 4059 ms 9196 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 4091 ms 263156 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 1 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 1 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 1 ms 364 KB Output is correct
2 Correct 1 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 -