Submission #904191

#	Time	Username	Problem	Language	Result	Execution time	Memory
904191		jamjanek	Giraffes (JOI22_giraffes)	C++14	100 / 100	3720 ms	2616 KiB

giraffes

#include<bits/stdc++.h>
using namespace std;

pair<int,int>tab[8010];
vector<pair<int,int>>points;
struct kwadrat{pair<int, int> A; pair<int,int>B;};

vector<kwadrat>warstwy[2];
int wynik, n;

pair<int,int>rotate(pair<int,int>A){
	int pomx = A.second;
	int pomy = n-A.first+1;
	return {pomx, pomy};
}
kwadrat rotateK(kwadrat A){
	A.A = rotate(A.A);
	A.B = rotate(A.B);
	swap(A.A.second, A.B.second);
	return A;
}

const int base = 1<<13;
const int inf = 1000000;
int tree[2*base];

void dodaj(int x, int w){
	x+=base;
	while(x>0){
		tree[x] = min(tree[x], w);
		x/=2;
	}
}
int query(int w, int l, int p, int a, int b){
	if(l>b || p<a)return inf;
	if(a<=l && p<=b)
		return tree[w];
	return min(query(w*2, l, (l+p)/2, a, b), query(w*2+1, (l+p)/2+1, p, a, b));
}

void policz(int w){
	vector<pair<int,int>>vec;
	vector<int>pom(n+1,inf);
	for(int i = 0;i<(int)warstwy[!w].size();i++)
		vec.push_back({warstwy[!w][i].A.first-warstwy[!w][i].A.second, (i+1)});
	for(int i=0;i<(int)points.size();i++)
		vec.push_back({points[i].first-points[i].second, -(i+1)});

	sort(vec.begin(), vec.end());
	for(auto &j:tree)j = inf;
	for(auto j: vec){
		if(j.second<0){
			int i = -j.second-1;
			int xd = query(1, 0, base-1, points[i].first+1, base-1);
			pom[i] = min(pom[i], xd-points[i].second);
//			printf("  %d %d %d\n", points[i].first, points[i].second, pom[i]);
		}
		else{
			int i = j.second-1;
			dodaj(warstwy[!w][i].A.first, warstwy[!w][i].B.second);
		}
	}
	reverse(vec.begin(), vec.end());
	for(auto &j:tree)j = inf;
	for(auto j: vec){
		if(j.second<0){
			int i = -j.second-1;
			int xd = query(1, 0, base-1, points[i].second+1, base-1);
			pom[i] = min(pom[i], xd-points[i].first);
//			printf("    %d %d %d\n", points[i].first, points[i].second, pom[i]);

		}
		else{
			int i = j.second-1;
			dodaj(warstwy[!w][i].A.second, warstwy[!w][i].B.first);
		}
	}
	for(int i=0;i<(int)points.size();i++)
		if(max(points[i].first, points[i].second)+pom[i]<=n)
			warstwy[w].push_back({{points[i].first, points[i].second}, {points[i].first+pom[i], points[i].second+pom[i]}});
//	for(int i=0;i<(int)points.size();i++)
//		printf("%d %d %d\n", points[i].first, points[i].second, pom[i]);
//	for(auto j: warstwy[w])
//		printf("%d %d %d %d\n", j.A.first, j.A.second, j.B.first, j.B.second);
//	printf("\n");
}

int main()
{
	int i, a;
	scanf("%d", &n);
	for(i=1;i<=n;i++){
		scanf("%d", &a);
		tab[i].first = i;
		tab[i].second = a;
		warstwy[0].push_back({{i, a}, {i,a}});
		points.push_back({i, a});
	}
	wynik = 0;	
	for(int w=1;warstwy[!w].size()>0;w^=1){
		wynik++;
//		printf("%d\n", wynik);
		warstwy[w].clear();
		for(i=0;i<4;i++){
			policz(w);
			for(auto &j: warstwy[!w])
				j = rotateK(j);
			for(auto &j: warstwy[w])
				j = rotateK(j);
			for(auto &j: points)
				j = rotate(j);
		}
//		for(auto j: warstwy[w])printf("%d %d %d %d\n", j.A.first, j.A.second, j.B.first, j.B.second);printf("\n");
//		exit(0);
	}
	
	printf("%d\n", n-wynik);
}

Compilation message (stderr)

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

• Subtask 1: 10 / 10
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 41 / 41