Submission #953323

#	Time	Username	Problem	Language	Result	Execution time	Memory
953323		WonderfulWhale	IOI Fever (JOI21_fever)	C++17	37 / 100	5034 ms	125024 KiB

fever

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

#define int int64_t
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

ostream& operator<<(ostream &os, pair<auto, auto> x) {
	os << "{" << x.nd/2 << ", " << x.st/2 << "}";
	return os;
}

const int MAXN = 100'009;
const int INF = 1e18;

int n;
pii tab[MAXN];
int dis[MAXN];
int dir[MAXN];
pii sdis[8][MAXN];
unordered_map<int, int> remap[4];

set<pii> S[8][MAXN];

int D(int x, int y) {
	// return abs(tab[x].st-tab[y].st)+abs(tab[x].nd-tab[y].nd);
	return max(abs(tab[x].st-tab[y].st), abs(tab[x].nd-tab[y].nd));
}

int id(int x, int i) {
	if(i%4==0) {
		return remap[i%4][tab[x].nd];
	}
	if(i%4==1) {
		return remap[i%4][tab[x].st-tab[x].nd];
	}
	if(i%4==2) {
		return remap[i%4][tab[x].st];
	}
	if(i%4==3) {
		return remap[i%4][tab[x].st+tab[x].nd];
	}
}

int f(int x, int i) {
	int ret = 0;
	if(i/2==0||i/2==2) {
		ret = tab[x].st;
	} else {
		ret = tab[x].nd;
	}
	if(i>=4) ret*=-1;
	return ret;
}

int opp(int x, int i) {
	if(x==i) {
		return (x+4)%8;
	}
	if((x+1)%8==i) {
		return (x+6)%8;
	}
	return (x+2)%8;
}

priority_queue<pii, vector<pii>, greater<pii>> Q;

void push(int x) {
	for(int i=0;i<8;i++) {
		int num = id(x, i);
		auto it = S[i][num].upper_bound({f(x, i), INF});
		if(it!=S[i][num].end()) {
			int nxt = (*it).nd;
			int X = 2-i%2;
			int ndis = sdis[i][x].st+D(x, nxt)/X;
			if(ndis<sdis[i][nxt].st) {
				sdis[i][nxt] = {ndis, sdis[i][x].nd};
			}
			if(ndis<dis[nxt]) {
				dis[nxt] = ndis;
				dir[nxt] = opp(sdis[i][x].nd, i);
				Q.push({dis[nxt], nxt});
				cerr << "PUSH!!!\n";
			}
		}
	}
}

int dijkstra(int I) {
	int ret = 0;
	fill(dis, dis+n, INF);
	fill(dir, dir+n, INF);
	for(int i=0;i<8;i++) {
		fill(sdis[i], sdis[i]+n, make_pair(INF, -1));
		// sdis[i][0] = 0;
	}
	dis[0] = 0;
	dir[0] = I;
	Q.push({0, 0});
	while(sz(Q)) {
		auto [x_dis, x] = Q.top();
		Q.pop();
		if(x_dis!=dis[x]) continue;
		cerr << "D: " << tab[x] << " " << dis[x] << "\n";
		cerr << "Direction: " << dir[x] << "\n";
		ret++;
		for(int i=0;i<8;i++) {
			S[i][id(x, i)].erase(make_pair(f(x, i), x));
		}
		push(x);
		int tmp = (dir[x]-1);
		if(tmp<0) tmp += 8;
		vector<int> v = {tmp, dir[x], (dir[x]+1)%8};
		for(int i:v) {
			cerr << "dir: " << i << "\n";
			int X = 2-i%2;
			auto it = S[i][id(x, i)].lower_bound(make_pair(f(x, i)+dis[x]*X, -1));
			cerr << "init: " << f(x, i) << "\n";
			cerr << "lim: " << f(x, i)+dis[x]/X << "\n";
			if(it!=S[i][id(x, i)].end()) {
				 cerr << "full find: " << (*it).st << " " << (*it).nd << "\n";
				int y = (*it).nd;
				// cerr << "cand: "<< tab[y] << "\n";
				int ndis = D(x, y)/X;
				if(ndis<sdis[i][y].st) {
					sdis[i][y] = {ndis, dir[x]};
				}
				if(ndis<dis[y]) {
					dis[y] = ndis;
					dir[y] = opp(dir[x], i);
					Q.push({dis[y], y});
				}
			}
		}
	}
	return ret;
}

int32_t main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cin >> n;
	vector<int> vals[4];
	for(int i=0;i<n;i++) {
		cin >> tab[i].st >> tab[i].nd;
		tab[i].st*=2, tab[i].nd*=2;
		swap(tab[i].st, tab[i].nd);
		vals[0].pb(tab[i].nd), vals[2].pb(tab[i].st);
		vals[1].pb(tab[i].st-tab[i].nd), vals[3].pb(tab[i].st+tab[i].nd);
	}
	for(int i=0;i<4;i++) {
		sort(all(vals[i]));
		vals[i].erase(unique(all(vals[i])), vals[i].end());
		for(int j=0;j<sz(vals[i]);j++) {
			remap[i][vals[i][j]] = j;
		}
	}
	// for(int i=0;i<n;i++) {
	// 	// cerr << "NOW: " << i << "\n";
	// 	for(int j=0;j<8;j++) {
	// 		S[j][id(i, j)].insert(make_pair(f(i, j), i));
	// 		// cerr << "id: " << id(i, j) << " : f: "<< f(i, j) << "\n";
	// 	}
	// }
	int ans = 0;
	// ans = dijkstra(2);
	for(int I=0;I<8;I+=2) {
		for(int i=0;i<n;i++) {
			for(int j=0;j<8;j++) {
				S[j][i].clear();
			}
		}
		for(int i=0;i<n;i++) {
			cerr << "NOW: " << i << "\n";
			for(int j=0;j<8;j++) {
				S[j][id(i, j)].insert(make_pair(f(i, j), i));
				cerr << "id: " << id(i, j) << " : f: "<< f(i, j) << "\n";
			}
		}
		ans = max(ans, dijkstra(I));
	}
	cout << ans << "\n";
}

Compilation message (stderr)

fever.cpp:12:39: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   12 | ostream& operator<<(ostream &os, pair<auto, auto> x) {
      |                                       ^~~~
fever.cpp:12:45: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   12 | ostream& operator<<(ostream &os, pair<auto, auto> x) {
      |                                             ^~~~
fever.cpp: In function 'int64_t id(int64_t, int64_t)':
fever.cpp:47:1: warning: control reaches end of non-void function [-Wreturn-type]
   47 | }
      | ^

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 12 / 12
• Subtask 6: 0 / 32
• Subtask 7: 0 / 31