oj.uz

Submission #1051733

# Submission time Handle Problem Language Result Execution time Memory
1051733 2024-08-10T09:22:04 Z pcc Comparing Plants (IOI20_plants) C++17
44 / 100
 3305 ms 66420 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;

#define pii pair<int,int>
#define fs first
#define sc second

const int mxn = 4e5+10;

int arr[mxn];
int N;
int K;
int perm[mxn];
int dp[mxn];
set<int> st;
set<pii> rng;

struct SEG{
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
	pii seg[mxn*4];
	void modify(int now,int l,int r,int s,int e,int v){
		if(l>=s&&e>=r){
			seg[now].sc += v;
			return;
		}
		if(mid>=s)modify(ls,l,mid,s,e,v);
		if(mid<e)modify(rs,mid+1,r,s,e,v);
		seg[now].fs = min(seg[ls].fs+seg[ls].sc,seg[rs].fs+seg[rs].sc);
		return;
	}
	int get_mn(int now,int l,int r){
		if(l == r){
			return l;
		}
		if(seg[ls].fs+seg[ls].sc<seg[rs].fs+seg[rs].sc)return get_mn(ls,l,mid);
		else return get_mn(rs,mid+1,r);
	}
#undef ls
#undef rs
#undef mid
}seg;


void add(int p){
	int nxt = *st.upper_bound(p);
	int pre = *(--st.upper_bound(p));
	rng.erase(pii(nxt-pre,nxt));
	rng.insert(pii(nxt-p,nxt));
	rng.insert(pii(p-pre,p));
	st.insert(p);
	return;
}

void del(int p){
	auto it = st.find(p);
	int pre = *prev(it),nxt = *next(it);
	rng.erase(pii(p-pre,p));
	rng.erase(pii(nxt-p,nxt));
	rng.insert(pii(nxt-pre,nxt));
	st.erase(p);
	return;
}

void calc(int id){
	auto it = rng.rbegin();
	if(it->sc >= N*2)it++;
	auto pos = it->sc;
	pos %= N;
	cerr<<id<<":"<<pos<<','<<it->fs<<endl;
	assert(it->fs>=K);
	del(pos);
	del(pos+N);
	perm[pos] = id;
	seg.modify(0,0,N*2-1,pos+N-K+1,pos+N,-1);
	seg.modify(0,0,N*2-1,max(pos-K+1,0),pos,-1);
	if(pos-K+1<0)seg.modify(0,0,N*2-1,N*2-1+(pos-K+1)+1,N*2-1,-1);
	while(seg.seg[0].fs+seg.seg[0].sc == 0){
		int p = seg.get_mn(0,0,N*2-1);
		p %= N;
		add(p);
		seg.modify(0,0,N*2-1,p,p,mxn*4);
		add(p+N);
		seg.modify(0,0,N*2-1,p+N,p+N,mxn*4);
	}
	return;
}

void init(int k, std::vector<int> r) {
	K = k;
	N = r.size();
	for(int i = 0;i<N;i++)arr[i] = arr[i+N] = r[i];
	int pre = -1;
	st.insert(-1);
	st.insert(N*2);
	rng.insert(pii(N*2+1,N*2));
	for(int i = 0;i<N*2;i++){
		if(!arr[i]){
			add(i);
		}
		if(arr[i])seg.modify(0,0,N*2-1,i,i,arr[i]);
		else seg.modify(0,0,N*2-1,i,i,mxn*4);
	}
	cerr<<"INIT!: "<<rng.rbegin()->fs<<endl;
	for(auto &i:rng)cerr<<i.fs<<','<<i.sc<<endl;
	for(int i = N-1;i>=0;i--)calc(i);
	for(int i = 0;i<N;i++)cerr<<perm[i]<<',';cerr<<endl;
}

int compare_plants(int x, int y) {
	return perm[x]>perm[y]?1:-1;
}

Compilation message

plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:109:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  109 |  for(int i = 0;i<N;i++)cerr<<perm[i]<<',';cerr<<endl;
      |  ^~~
plants.cpp:109:43: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  109 |  for(int i = 0;i<N;i++)cerr<<perm[i]<<',';cerr<<endl;
      |                                           ^~~~
plants.cpp:95:6: warning: unused variable 'pre' [-Wunused-variable]
   95 |  int pre = -1;
      |      ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Correct 0 ms 4444 KB Output is correct
4 Incorrect 0 ms 4444 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 4444 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Correct 0 ms 4544 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 9 ms 4444 KB Output is correct
7 Correct 65 ms 7780 KB Output is correct
8 Correct 2 ms 4440 KB Output is correct
9 Correct 9 ms 4648 KB Output is correct
10 Correct 64 ms 7796 KB Output is correct
11 Correct 82 ms 8016 KB Output is correct
12 Correct 62 ms 7788 KB Output is correct
13 Correct 71 ms 7764 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Correct 0 ms 4544 KB Output is correct
4 Correct 0 ms 4444 KB Output is correct
5 Correct 1 ms 4444 KB Output is correct
6 Correct 9 ms 4444 KB Output is correct
7 Correct 65 ms 7780 KB Output is correct
8 Correct 2 ms 4440 KB Output is correct
9 Correct 9 ms 4648 KB Output is correct
10 Correct 64 ms 7796 KB Output is correct
11 Correct 82 ms 8016 KB Output is correct
12 Correct 62 ms 7788 KB Output is correct
13 Correct 71 ms 7764 KB Output is correct
14 Correct 211 ms 8900 KB Output is correct
15 Correct 1705 ms 22352 KB Output is correct
16 Correct 185 ms 11088 KB Output is correct
17 Correct 1659 ms 26088 KB Output is correct
18 Correct 2589 ms 46276 KB Output is correct
19 Correct 1662 ms 26352 KB Output is correct
20 Correct 1640 ms 26372 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 61 ms 7392 KB Output is correct
4 Correct 2224 ms 35968 KB Output is correct
5 Correct 1882 ms 25160 KB Output is correct
6 Correct 1803 ms 22432 KB Output is correct
7 Correct 2007 ms 25764 KB Output is correct
8 Correct 1892 ms 26180 KB Output is correct
9 Correct 2224 ms 35432 KB Output is correct
10 Correct 1818 ms 28640 KB Output is correct
11 Correct 3305 ms 66420 KB Output is correct
12 Correct 1602 ms 25684 KB Output is correct
13 Correct 2974 ms 54100 KB Output is correct

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4440 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Incorrect 1 ms 4440 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 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Incorrect 0 ms 4444 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 4444 KB Output is correct
2 Correct 0 ms 4444 KB Output is correct
3 Correct 0 ms 4444 KB Output is correct
4 Incorrect 0 ms 4444 KB Output isn't correct
5 Halted 0 ms 0 KB -