QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#249488#7569. LinesUSP_USP_USPTL 1ms3520kbC++206.3kb2023-11-12 10:05:032023-11-12 10:05:03

Judging History

你现在查看的是最新测评结果

  • [2023-11-12 10:05:03]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3520kb
  • [2023-11-12 10:05:03]
  • 提交

answer

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

#define all(x) x.begin(), x.end()
#define int int64_t
#define pb push_back

void dbg_out() { cerr << endl; }
template <typename H, typename... T>
void dbg_out(H h, T... t) { cerr << ' ' << h; dbg_out(t...); }
#define dbg(...) { cerr << #__VA_ARGS__ << ':'; dbg_out(__VA_ARGS__); }

#define fi first
#define se second

using ll = long long;

using db = long double;

struct pt{
    long long x, y;
    pt operator + (const pt & p) const {
        return pt{x + p.x, y + p.y};
    }
    pt operator - (const pt & p) const {
        return pt{x - p.x, y - p.y};
    }
    long long cross(const pt & p) const {
        return x * p.y - y * p.x;
    }
};

struct Point {
	double x, y;	

	bool operator <(const Point &p) const {
		if(x == p.x) return y < p.y;
		return x < p.x;
	}
};

double cross(const Point &O, const Point &A, const Point &B)
{
	return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

vector<pair<int,int>> convex_hull(vector<pair<int,int>> q)
{
	vector<Point> P(q.size());
	int n = q.size();
	for(int i = 0; i < n; i++){
		P[i].y = q[i].fi;
		P[i].x = q[i].se;
	}
	int k = 0;
	vector<Point> H(2*n);

	sort(P.begin(), P.end());

	// Lower hull
	for (int i = 0; i < n; ++i) {
		while (k >= 2 && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
		H[k++] = P[i];
	}

	// Upper hull
	for (int i = n-2, t = k+1; i >= 0; i--) {
		while (k >= t && cross(H[k-2], H[k-1], P[i]) <= 0) k--;
		H[k++] = P[i];
	}
	if(n != 1)
		H.resize(k-1);
	else H.resize(1);

	vector<pair<int,int>> ret;
	for(auto p : H){
		int l = p.x;
		int r = p.y;
		ret.pb({l,r});
	}
	return ret;

}

void reorder_polygon(vector<pt> & P){
    size_t pos = 0;
    for(size_t i = 1; i < P.size(); i++){
        if(P[i].y < P[pos].y || (P[i].y == P[pos].y && P[i].x < P[pos].x))
            pos = i;
    }
    rotate(P.begin(), P.begin() + pos, P.end());
}



vector<pt> minkowski(vector<pt> P, vector<pt> Q){
    // the first vertex must be the lowest
    reorder_polygon(P);
    reorder_polygon(Q);
    // we must ensure cyclic indexing
    P.push_back(P[0]);
    P.push_back(P[1]);
    Q.push_back(Q[0]);
    Q.push_back(Q[1]);
    // main part
    vector<pt> result;
    size_t i = 0, j = 0;
    while(i < P.size() - 2 || j < Q.size() - 2){
        result.push_back(P[i] + Q[j]);
        auto cross = (P[i + 1] - P[i]).cross(Q[j + 1] - Q[j]);
        if(cross >= 0 && i < P.size() - 2)
            ++i;
        if(cross <= 0 && j < Q.size() - 2)
            ++j;
    }
    return result;
}

struct CHT {
    int it;
    vector<ll> a, b;
    CHT():it(0){}
	
    bool useless(){
        int sz = a.size();
        int r = sz-1, m = sz-2, l = sz-3;
        return (b[l] - b[r]) * (a[m] - a[l]) <= (b[l] - b[m]) * (a[r] - a[l]);
    }
    void add(ll A, ll B){
        a.push_back(A); b.push_back(B);
        while (!a.empty()){
            if ((a.size() < 3) || !useless()) break;
            a.erase(a.end() - 2);
            b.erase(b.end() - 2);
        }
    }
};

void solve() {
    int n;
    cin >> n;
    vector<int> a(n+1), b(n+1), c(n+1);
    vector<int> ok(3*n+1);
    for(int i = 0; i <= n; i++)
        cin >> a[i];
    for(int i = 0; i <= n; i++)
        cin >> b[i];
    for(int i = 0 ; i <= n; i++)
        cin >> c[i];
	
    vector<array<int,2>> sad;
	auto calcmaq = [&](vector<int> v){
		vector<pair<int,int>> mq;
		for(int i = 0; i <= n; i++){
			while(!mq.empty() && mq.back().fi <= v[i]) mq.pop_back();
			mq.push_back({v[i],i});
		}
		return mq;
	};

	auto cross = [&] (pair<int, int> x, pair<int, int> y) {
		return x.first * y.second - y.first * x.second;
	};
	assert (cross ({1, 0}, {1, 1}) > 0);

	auto is_left = [&] (pair<int, int> r1, pair<int, int> r2, pair<int, int> x) {
		// queremos ver se x esta na esquerda de r1, r2

		r2.first -= r1.first;
		r2.second -= r1.second;

		x.first -= r1.first;
		x.second -= r1.second;

		return cross (r2, x) > 0;
	};

	auto fix = [&] (vector<pair<int, int>> points) {
		/*
		for (auto &[y, x] : points) swap (y, x);

		CHT cht;

		for (auto [x, y] : points) {
			cht.add(x,y);
		}
		vector<pair<int,int>> wtf;
		int sz = cht.a.size();
		for(int i = 0; i < sz; i++){
			int A = cht.a[i];
			int B = cht.b[i];
			wtf.pb({B,A});
		}
		return wtf;
		*/

		for (auto &[y, x] : points) swap (y, x);
		sort(points.begin(),points.end());

		vector<pair<int, int>> hull;
		for (auto [x, y] : points) {
			hull.pb ({x, y});

			while (hull.size () > 2) {
				// tenho que ver se o ponto hull[-2] esta na esquerda da reta [hull[-1], hull[-3]]

				pair<int, int> r1 = end (hull)[-1], r2 = end (hull)[-3], X = end (hull)[-2];

				if (is_left (r1, r2, X)) {
					hull.erase (hull.end() - 2);
				}
				else break;
			}
		}

		//for (auto &[x, y] : hull) swap (x, y);
		return hull;
	};

	for(int q = 0; q < 2; q++){
		auto ma = calcmaq(a);
		auto mb = calcmaq(b);
		auto mc = calcmaq(c);
		// for (auto u : ma) cout << u.first << " ";
		// cout << "\n";
		ma = convex_hull(ma);
		mb = convex_hull(mb);
		mc = convex_hull(mc);
		vector<pt> Pa,Pb,Pc;

		for(auto [ida,va] : ma){
			if(q){
				ida = n-ida;
			}
			Pa.pb({ida,va});
		}
		for(auto [idb,vb] : mb){
			if(q){
				idb = n-idb;
			}
			Pb.pb({idb,vb});
		}
		for(auto [idc,vc] : mc){
			if(q){
				idc = n-idc;
			}
			Pc.pb({idc,vc});
		}
		auto ret1 = minkowski(Pa,Pb);
		auto ret2 = minkowski(ret1,Pc);
		for(auto [x,y] : ret2){
			sad.pb({x,y});
		}

		// for (auto u : ma) cout << u.first << " ";
		// cout << "\n";
		reverse(a.begin(),a.end());
		reverse(b.begin(),b.end());
		reverse(c.begin(),c.end());
	}
	sad.pb({0,a[0]+b[0]+c[0]});
	sad.pb({3*n,a[n]+b[n]+c[n]});
	sort(sad.begin(),sad.end());
	sort (all (sad));
	sad.resize (unique (all (sad)) - sad.begin ());

	CHT cht;
	for(auto [A,B] : sad){
		cht.add(A,B);
	}
	for(auto fe : cht.a){
		ok[fe] = 1;
	}
	vector<int> ans;
	for(int i = 0; i <= 3*n; i++){
		if(!ok[i]) ans.pb(i);
	}
	cout << ans.size() << '\n';
	for(auto x : ans ) cout << x << ' ';
	cout << '\n';

}

signed main(){
	ios::sync_with_stdio(false); cin.tie(0);
	solve();
}

/*
Makefile:
CXXFLAGS=-Wall -Wextra -Wshadow -g -pedantic -fsanitize=address,undefined -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUGPEDANTIC -std=gnu++17
 */

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3520kb

input:

3
3 1 8 7
9 1 3 1
5 1 1 6

output:

5
1 3 4 7 8 

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 0ms
memory: 3492kb

input:

1
1 2
1 2
1 2

output:

2
1 2 

result:

ok 3 number(s): "2 1 2"

Test #3:

score: -100
Time Limit Exceeded

input:

252
336470888 634074578 642802746 740396295 773386884 579721198 396628655 503722503 971207868 202647942 2087506 268792718 46761498 443917727 16843338 125908043 691952768 717268783 787375312 150414369 693319712 519096230 45277106 856168102 762263554 674936674 407246545 274667941 279198849 527268921 1...

output:


result: