제출 #917212

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
917212		jamjanek	Seesaw (JOI22_seesaw)	C++14	100 / 100	1047 ms	45160 KiB

seesaw

#include<bits/stdc++.h>
using namespace std;
int A[200010];
long long sumy[200010];

struct node{
	long double srodek;
	int l, r;
	bool zapalony;
};
vector<node>tab[200010];

const int base = 1<<18;
bool tree[2*base][2][2];

void update(int x){
	x/=2;
	while(x>0){
		tree[x][0][0] = (tree[x*2][0][0]&tree[x*2+1][0][0])|(tree[x*2][0][1]&tree[x*2+1][1][0]);
		tree[x][0][1] = (tree[x*2][0][0]&tree[x*2+1][0][1])|(tree[x*2][0][1]&tree[x*2+1][1][1]);
		tree[x][1][0] = (tree[x*2][1][0]&tree[x*2+1][0][0])|(tree[x*2][1][1]&tree[x*2+1][1][0]);
		tree[x][1][1] = (tree[x*2][1][0]&tree[x*2+1][0][1])|(tree[x*2][1][1]&tree[x*2+1][1][1]);
		x/=2;
	}
}

void dodaj(int i, int j){
	tab[i][j].zapalony = 1;
	auto &ja = tab[i][j];
	for(int a=0;a<(int)tab[i-1].size();a++){
		auto &pop = tab[i-1][a];
		if(abs(pop.l-ja.l)+abs(pop.r-ja.r)==1 && pop.zapalony){
			tree[base+i-1][a][j] = 1;
			update(base+i-1);
		}
	}
	for(int a=0;a<(int)tab[i+1].size();a++){
		auto &pop = tab[i+1][a];
		if(abs(pop.l-ja.l)+abs(pop.r-ja.r)==1 && pop.zapalony){
			tree[base+i][j][a] = 1;
			update(base+i);
		}
	}
	
}

void usun(int i, int j){
	tab[i][j].zapalony = 0;
	auto &ja = tab[i][j];
	for(int a=0;a<(int)tab[i-1].size();a++){
		auto &pop = tab[i-1][a];
		if(abs(pop.l-ja.l)+abs(pop.r-ja.r)==1){
			tree[base+i-1][a][j] = 0;
			update(base+i-1);
		}
	}
	for(int a=0;a<(int)tab[i+1].size();a++){
		auto &pop = tab[i+1][a];
		if(abs(pop.l-ja.l)+abs(pop.r-ja.r)==1){
			tree[base+i][j][a] = 0;
			update(base+i);
		}
	}
}
vector<vector<bool>>pom;

void zapytaj(int w, int l, int p, int a, int b){
	if(l>b || p<a)return;
	if(a<=l && p<=b){
		pom.push_back({tree[w][0][0], tree[w][0][1], tree[w][1][0], tree[w][1][1]});
		return;
	}
	zapytaj(w*2, l, (l+p)/2, a, b);
	zapytaj(w*2+1, (l+p)/2+1, p, a, b);
}

bool Da_sie(int l, int r){
	pom.clear();
	zapytaj(1, 0, base-1, l, r);
	for(int i=1;i<(int)pom.size();i++){
		vector<bool>nast={0,0,0,0};
		nast[0] = (pom[0][0]&pom[i][0])|(pom[0][1]&pom[i][2]);
		nast[1] = (pom[0][0]&pom[i][1])|(pom[0][1]&pom[i][3]);
		nast[2] = (pom[0][2]&pom[i][0])|(pom[0][3]&pom[i][2]);
		nast[3] = (pom[0][2]&pom[i][1])|(pom[0][3]&pom[i][3]);
		pom[0] = nast;
	}
	return pom[0][0]|pom[0][1]|pom[0][2]|pom[0][3];
}

int main()
{
	int n, i;
	scanf("%d", &n);
	for(i=1;i<=n;i++){
		scanf("%d", &A[i]);
		sumy[i]=sumy[i-1]+A[i];
	}
	long double srodek = (long double)sumy[n]/n;
	tab[n].push_back({srodek, 1, n});
	for(i=n;i>1;i--){
		vector<node>kolejna;
		for(auto j: tab[i]){
			kolejna.push_back({ ((long double)sumy[j.r-1]-sumy[j.l-1])/(j.r-j.l), j.l, j.r-1});
			kolejna.push_back({ ((long double)sumy[j.r]-sumy[j.l])/(j.r-j.l), j.l+1, j.r});
		}
		while(kolejna.size()>=2 && kolejna[kolejna.size()-2].srodek>=srodek)kolejna.pop_back();
		reverse(kolejna.begin(), kolejna.end());
		while(kolejna.size()>=2 && kolejna[kolejna.size()-2].srodek<=srodek)kolejna.pop_back();
		reverse(kolejna.begin(), kolejna.end());
		tab[i-1] = kolejna;
	}
	/*
	for(i=1;i<=n;i++){
		printf("%d:\n", i);
		for(auto j: tab[i])
			printf("%Lf %d %d\n", j.srodek, j.l, j.r);
	}*/
	vector<pair<long double, pair<int,int>>>sorted;
	for(i=1;i<=n;i++)
		for(int j=0;j<(int)tab[i].size();j++)
			sorted.push_back({tab[i][j].srodek, {i, j}});
	sort(sorted.begin(), sorted.end());
//	for(auto j: sorted)printf("{%Lf %d %d}, ", j.first, j.second.first, j.second.second);printf("\n");
	dodaj(sorted[0].second.first, sorted[0].second.second);
	int L=0, R=0;
	long double wynik = 1000000000;
	while(R<(int)sorted.size()){
//		printf("L=%d R=%d, %d\n", L, R, (int)Da_sie(0, n-2));
//		for(i=0;i<4;i++)printf("%d %d %d %d      ", (int)tree[base+i][0][0], (int)tree[base+i][0][1], (int)tree[base+i][1][0], (int)tree[base+i][1][1]);printf("\n");
		if(Da_sie(1, n-1)){
			wynik = min(wynik, sorted[R].first-sorted[L].first);
			usun(sorted[L].second.first, sorted[L].second.second);
			L++;
		}
		else{
			R++;
			if(R==(int)sorted.size())break;
			dodaj(sorted[R].second.first, sorted[R].second.second);
		}
	}
	printf("%Lf\n", wynik);
}

컴파일 시 표준 에러 (stderr) 메시지

seesaw.cpp: In function 'int main()':
seesaw.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
seesaw.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |   scanf("%d", &A[i]);
      |   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 33 / 33
• Subtask 3: 33 / 33
• Subtask 4: 33 / 33