oj.uz

Submission #367380

# Submission time Handle Problem Language Result Execution time Memory
367380 2021-02-17T05:10:22 Z kig9981 Shortcut (IOI16_shortcut) C++17
0 / 100
 1 ms 492 KB 
#include "shortcut.h"
#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

const long long INF=0x7fffffffffffffffLL;
vector<pair<long long,int>> L, R;
int N, C, D[1000000];
long long PS[1000000];

void set_value(long long &x1, long long &y1, long long &x2, long long &y2, int x, int y, long long l)
{
	x1=max(x1,PS[x]+PS[y]-(l-D[x]-D[y]-C));
	y1=max(y1,PS[x]-PS[y]-(l-D[x]-D[y]-C));
	x2=min(x2,PS[x]+PS[y]+(l-D[x]-D[y]-C));
	y2=min(y2,PS[x]-PS[y]+(l-D[x]-D[y]-C));
}

bool solve(long long l)
{
	long long x1=-INF, y1=-INF, x2=INF, y2=INF, mv=INF, mv2=INF;
	int j=0, m=-1, m2=-1;
	for(int i=0;i<N;i++) {
		while(j<N && R[j].first>l+L[i].first) {
			int c=R[j++].second;
			if(PS[c]-D[c]<mv) {
				mv2=mv;
				mv=PS[c]-D[c];
				m2=m;
				m=c;
			}
			else if(PS[c]-D[c]<mv2) {
				mv2=PS[c]-D[c];
				m2=c;
			}
		}
		if(j==0 || j==1 && L[i].second==R[0].second || R[j-1].first<=l+L[i].first) continue;
		if(R[0].second==L[i].second) {
			if(R[1].first>l+L[i].first) set_value(x1,y1,x2,y2,L[i].second,R[1].second,l);
		}
		else if(R[0].first>l+L[i].first) set_value(x1,y1,x2,y2,L[i].second,R[0].second,l);
		set_value(x1,y1,x2,y2,L[i].second,(L[i].second==m ? m2:m),l);
	}
	if(x1>x2 || y1>y2) return false;
	for(int i=j=0;i<N;i++) {
		while(j<i && (PS[j]+PS[i]<x1 || PS[j]-PS[i]<y1)) j++;
		while(j>0 && (PS[j-1]+PS[i]>x2 || PS[j-1]-PS[i]>y2)) j--;
		if(0<=j && j<i && PS[j]+PS[i]>=x1 && PS[j]-PS[i]>=y1 && PS[j]+PS[i]<=x2 && PS[j]-PS[i]<=y2) return true;
	}
	return false;
}

long long find_shortcut(int n, vector<int> l, vector<int> d, int c)
{
	int mx=d[0], mx2=0;
	long long s, e;
	N=n; C=c; L.emplace_back(-d[0],0); R.emplace_back(e=D[0]=d[0],0);
	for(int i=1;i<N;i++) {
		PS[i]=PS[i-1]+l[i-1];
		e+=D[i]=d[i];
		L.emplace_back(PS[i]-d[i],i);
		R.emplace_back(PS[i]+d[i],i);
		if(mx<d[i]) {
			mx2=mx;
			mx=d[i];
		}
		else if(mx2<d[i]) mx2=d[i];
	}
	s=mx+mx2; e+=PS[N-1];
	sort(L.rbegin(),L.rend());
	sort(R.rbegin(),R.rend());
	while(s<=e) {
		long long m=(s+e)>>1;
		if(solve(m)) e=m-1;
		else s=m+1;
	}
    return s;
}

Compilation message

shortcut.cpp: In function 'bool solve(long long int)':
shortcut.cpp:45:19: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   45 |   if(j==0 || j==1 && L[i].second==R[0].second || R[j-1].first<=l+L[i].first) continue;
      |              ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB n = 4, 80 is a correct answer
2 Correct 1 ms 364 KB n = 9, 110 is a correct answer
3 Correct 1 ms 364 KB n = 4, 21 is a correct answer
4 Correct 1 ms 364 KB n = 3, 4 is a correct answer
5 Correct 1 ms 364 KB n = 2, 62 is a correct answer
6 Correct 1 ms 364 KB n = 2, 3 is a correct answer
7 Correct 1 ms 364 KB n = 3, 29 is a correct answer
8 Correct 1 ms 364 KB n = 2, 3 is a correct answer
9 Correct 1 ms 364 KB n = 2, 3 is a correct answer
10 Correct 1 ms 364 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 364 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 364 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 364 KB n = 3, 3000000000 is a correct answer
14 Incorrect 1 ms 364 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB n = 4, 80 is a correct answer
2 Correct 1 ms 364 KB n = 9, 110 is a correct answer
3 Correct 1 ms 364 KB n = 4, 21 is a correct answer
4 Correct 1 ms 364 KB n = 3, 4 is a correct answer
5 Correct 1 ms 364 KB n = 2, 62 is a correct answer
6 Correct 1 ms 364 KB n = 2, 3 is a correct answer
7 Correct 1 ms 364 KB n = 3, 29 is a correct answer
8 Correct 1 ms 364 KB n = 2, 3 is a correct answer
9 Correct 1 ms 364 KB n = 2, 3 is a correct answer
10 Correct 1 ms 364 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 364 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 364 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 364 KB n = 3, 3000000000 is a correct answer
14 Incorrect 1 ms 364 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB n = 4, 80 is a correct answer
2 Correct 1 ms 364 KB n = 9, 110 is a correct answer
3 Correct 1 ms 364 KB n = 4, 21 is a correct answer
4 Correct 1 ms 364 KB n = 3, 4 is a correct answer
5 Correct 1 ms 364 KB n = 2, 62 is a correct answer
6 Correct 1 ms 364 KB n = 2, 3 is a correct answer
7 Correct 1 ms 364 KB n = 3, 29 is a correct answer
8 Correct 1 ms 364 KB n = 2, 3 is a correct answer
9 Correct 1 ms 364 KB n = 2, 3 is a correct answer
10 Correct 1 ms 364 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 364 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 364 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 364 KB n = 3, 3000000000 is a correct answer
14 Incorrect 1 ms 364 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB n = 4, 80 is a correct answer
2 Correct 1 ms 364 KB n = 9, 110 is a correct answer
3 Correct 1 ms 364 KB n = 4, 21 is a correct answer
4 Correct 1 ms 364 KB n = 3, 4 is a correct answer
5 Correct 1 ms 364 KB n = 2, 62 is a correct answer
6 Correct 1 ms 364 KB n = 2, 3 is a correct answer
7 Correct 1 ms 364 KB n = 3, 29 is a correct answer
8 Correct 1 ms 364 KB n = 2, 3 is a correct answer
9 Correct 1 ms 364 KB n = 2, 3 is a correct answer
10 Correct 1 ms 364 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 364 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 364 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 364 KB n = 3, 3000000000 is a correct answer
14 Incorrect 1 ms 364 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB n = 4, 80 is a correct answer
2 Correct 1 ms 364 KB n = 9, 110 is a correct answer
3 Correct 1 ms 364 KB n = 4, 21 is a correct answer
4 Correct 1 ms 364 KB n = 3, 4 is a correct answer
5 Correct 1 ms 364 KB n = 2, 62 is a correct answer
6 Correct 1 ms 364 KB n = 2, 3 is a correct answer
7 Correct 1 ms 364 KB n = 3, 29 is a correct answer
8 Correct 1 ms 364 KB n = 2, 3 is a correct answer
9 Correct 1 ms 364 KB n = 2, 3 is a correct answer
10 Correct 1 ms 364 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 364 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 364 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 364 KB n = 3, 3000000000 is a correct answer
14 Incorrect 1 ms 364 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #6
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB n = 4, 80 is a correct answer
2 Correct 1 ms 364 KB n = 9, 110 is a correct answer
3 Correct 1 ms 364 KB n = 4, 21 is a correct answer
4 Correct 1 ms 364 KB n = 3, 4 is a correct answer
5 Correct 1 ms 364 KB n = 2, 62 is a correct answer
6 Correct 1 ms 364 KB n = 2, 3 is a correct answer
7 Correct 1 ms 364 KB n = 3, 29 is a correct answer
8 Correct 1 ms 364 KB n = 2, 3 is a correct answer
9 Correct 1 ms 364 KB n = 2, 3 is a correct answer
10 Correct 1 ms 364 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 364 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 364 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 364 KB n = 3, 3000000000 is a correct answer
14 Incorrect 1 ms 364 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #7
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB n = 4, 80 is a correct answer
2 Correct 1 ms 364 KB n = 9, 110 is a correct answer
3 Correct 1 ms 364 KB n = 4, 21 is a correct answer
4 Correct 1 ms 364 KB n = 3, 4 is a correct answer
5 Correct 1 ms 364 KB n = 2, 62 is a correct answer
6 Correct 1 ms 364 KB n = 2, 3 is a correct answer
7 Correct 1 ms 364 KB n = 3, 29 is a correct answer
8 Correct 1 ms 364 KB n = 2, 3 is a correct answer
9 Correct 1 ms 364 KB n = 2, 3 is a correct answer
10 Correct 1 ms 364 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 364 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 364 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 364 KB n = 3, 3000000000 is a correct answer
14 Incorrect 1 ms 364 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -

Subtask #8
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB n = 4, 80 is a correct answer
2 Correct 1 ms 364 KB n = 9, 110 is a correct answer
3 Correct 1 ms 364 KB n = 4, 21 is a correct answer
4 Correct 1 ms 364 KB n = 3, 4 is a correct answer
5 Correct 1 ms 364 KB n = 2, 62 is a correct answer
6 Correct 1 ms 364 KB n = 2, 3 is a correct answer
7 Correct 1 ms 364 KB n = 3, 29 is a correct answer
8 Correct 1 ms 364 KB n = 2, 3 is a correct answer
9 Correct 1 ms 364 KB n = 2, 3 is a correct answer
10 Correct 1 ms 364 KB n = 2, 2000000001 is a correct answer
11 Correct 1 ms 364 KB n = 2, 3000000000 is a correct answer
12 Correct 1 ms 364 KB n = 3, 3000000000 is a correct answer
13 Correct 1 ms 364 KB n = 3, 3000000000 is a correct answer
14 Incorrect 1 ms 364 KB n = 4, incorrect answer: jury 3000000001 vs contestant 4000000000
15 Halted 0 ms 0 KB -