QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#303839 | #7569. Lines | ELDRVD | WA | 1ms | 9668kb | C++14 | 2.1kb | 2024-01-13 00:44:41 | 2024-01-13 00:44:43 |
Judging History
answer
//https://qoj.ac/contest/1382/problem/7569
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define PI acos(-1)
#define LSB(i) ((i) & -(i))
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define sc second
#define th third
#define fo fourth
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ldb double
#define INF 1e15
#define MOD 1000000007
#define endl "\n"
#define all(data) data.begin(),data.end()
#define TYPEMAX(type) std::numeric_limits<type>::max()
#define TYPEMIN(type) std::numeric_limits<type>::min()
#define MAXN 300007
vector<ll> h[3];
ll n;
pll a[3][MAXN];
bool mm[3*MAXN];
vector<ll> Convex_Hull(pll b[])
{
vector<ll> ch;
for(int i=0;i<=n;i++)
{
while(ch.size()>=2 && b[ch[ch.size()-2]].fi-b[ch.back()].fi*(i-ch.back())>=(b[ch.back()].fi-b[i].fi)*(ch.back()-ch[ch.size()-2])) ch.pop_back();
ch.pb(i);
}
return ch;
}
bool cmp(ll x,ll y)
{
ll x1=h[x][h[x].size()-2],y1=h[x].back(),x2=h[y][h[y].size()-2],y2=h[y].back();
if((a[x][x1].fi-a[x][y1].fi)*(y2-x2)<(a[y][x2].fi-a[y][y2].fi)*(y1-x1)) return true;
return false;
}
int main(){
ios::sync_with_stdio(false); cin.tie(0);
cin>>n; mm[3*n]=true;
for(int i=0;i<3;i++)
{
for(int j=0;j<=n;j++) {cin>>a[i][j].fi; a[i][j].sc=j;}
h[i]=Convex_Hull(a[i]);
}
while(true)
{
ll dd=0; bool check[3];
for(int i=0;i<3;i++) check[i]=false;
for(int i=0;i<3;i++)
{
if(h[i].size()==1) continue;
bool checkk=true;
for(int j=0;j<3;j++)
{
if(i==j || h[j].size()==1) continue;
if(cmp(i,j)) checkk=false;
}
if(checkk) check[i]=true;
}
if(!check[0] && !check[1] && !check[2]) break;
for(int i=0;i<3;i++)
{
if(check[i]) h[i].pop_back();
dd+=h[i].back();
}
mm[dd]=true;
}
vector<ll> rez;
for(int i=0;i<=3*n;i++)
{
if(!mm[i]) rez.pb(i);
}
cout<<rez.size()<<endl;
for(auto dd:rez) cout<<dd<<" ";
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7596kb
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: 1ms
memory: 7696kb
input:
1 1 2 1 2 1 2
output:
2 1 2
result:
ok 3 number(s): "2 1 2"
Test #3:
score: -100
Wrong Answer
time: 0ms
memory: 9668kb
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:
505 4 6 7 8 11 12 14 15 17 18 21 22 24 25 27 29 30 32 34 35 38 39 41 42 44 46 49 51 52 54 56 57 61 62 63 65 68 70 72 73 74 75 76 78 80 81 83 85 86 87 90 91 92 94 95 96 97 98 100 102 103 104 105 106 108 109 111 112 113 114 116 117 118 119 121 122 123 126 127 128 131 132 133 135 136 137 139 140 141 14...
result:
wrong answer 1st numbers differ - expected: '733', found: '505'