oj.uz

Submission #945759

# Submission time Handle Problem Language Result Execution time Memory
945759 2024-03-14T07:24:03 Z WongChun1234 Rail (IOI14_rail) C++14
0 / 100
 443 ms 94864 KB 
#include<bits/stdc++.h>
#include"rail.h"
using namespace std;
 
const int N=5050;
int dist[N][4],rf,rrf;
vector<pair<int,int>> srt,ans,l,r;
map<int,int> id;
 
void eat(int i,int pos,int ty){
	//cerr<<i<<" at pos "<<pos<<" type "<<ty<<endl;
	ans[i]={pos,ty};
	id[pos]=i;
}
void findLocation(int n, int first, int location[], int stype[]) {
	int q=100000050;
	ans.resize(n);
	for (int i=-1000000;i<=1000000;i++) id[i]=5049;
	for (int i=1;i<n;i++){
		dist[i][0]=getDistance(0,i);
		srt.push_back({dist[i][0],i});
	}
	sort(srt.begin(),srt.end());
	rrf=rf=srt[0].second;
	eat(0,0,1);
	eat(rf,srt[0].first,2);
	for (int i=1;i<n;i++){
		if (i==rf) continue;
		dist[i][1]=getDistance(rf,i);
		if (dist[i][1]+dist[rf][0]==dist[i][0]){
			l.push_back({dist[i][1],i});
		}else{
			r.push_back({dist[i][0],i});
		}
	}
	sort(l.begin(),l.end());
	sort(r.begin(),r.end());
	for (pair<int,int> i:r){
		cerr<<i.first<<" "<<i.second<<" !!\n";
		int dis,ps;
		dist[i.second][2]=getDistance(rf,i.second);
		assert(!((dist[i.second][2]+dist[rf][0]-dist[i.second][0])%2));
		dis=(dist[i.second][2]+dist[rf][0]-dist[i.second][0])/2;
		ps=dist[rf][0]-dis;
		if (ans[id[ps]].second==1){
			//          -------------->
			//          |----
			// ------------->
			eat(i.second,dist[i.second][0],2);
			rf=i.second;
		}else{
			//      <---------
			//           D   |
			// -------------->
			eat(i.second,dist[rf][0]-dist[i.second][2],1);
		}
	}
	if (l.size()){
		rf=l[0].second;
		eat(rf,dist[rrf][0]-dist[rf][1],1);
		l.erase(l.begin(),next(l.begin()));
		for (pair<int,int> i:l){
			cerr<<i.first<<" "<<i.second<<" ??\n";
			int dis,ps;
			dist[i.second][2]=getDistance(rf,i.second);
			assert(!((dist[i.second][2]+dist[rf][0]-dist[i.second][0])%2));
			dis=(dist[i.second][2]+dist[rf][0]-dist[i.second][0])/2;
			ps=ans[rf].first+dis;
			if (ans[id[ps]].second==2){
				//     <--------------D
				//     |----       ----
				// <--------
				eat(i.second,dist[rrf][0]-dist[i.second][1],1);
				rf=i.second;
			}else{
				// <------------------D
				// |    C          ----
				// -------->
				eat(i.second,ans[rf].first+dist[i.second][2],2);
			}
		}
	}
	int mn=ans[0].first-first;
	for (int i=0;i<n;i++){
		location[i]=ans[i].first+mn;
		stype[i]=ans[i].second;
	}
}

Compilation message

rail.cpp: In function 'void findLocation(int, int, int*, int*)':
rail.cpp:16:6: warning: unused variable 'q' [-Wunused-variable]
   16 |  int q=100000050;
      |      ^

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 352 ms 94452 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 375 ms 94552 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 443 ms 94748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 443 ms 94864 KB Output isn't correct
2 Halted 0 ms 0 KB -