Submission #252368

#TimeUsernameProblemLanguageResultExecution timeMemory
252368shayan_pCircle selection (APIO18_circle_selection)C++17
7 / 100
3099 ms15096 KiB
// And you curse yourself for things you never done #include<bits/stdc++.h> #define F first #define S second #define PB push_back #define sz(s) int((s).size()) #define bit(n,k) (((n)>>(k))&1) using namespace std; typedef long long ll; typedef pair<int,int> pii; const int maxn = 3e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10; pair<pii, int> p[maxn]; int arr[maxn]; pii operator - (pii a, pii b){ return {a.F - b.F, a.S - b.S}; } pii operator + (pii a, pii b){ return {a.F + b.F, a.S + b.S}; } ll operator ^ (pii a, pii b){ return 1ll * a.F * b.F + 1ll * a.S * b.S; } bool ok(int i, int j){ return 1ll * (p[j].S + p[i].S) * (p[j].S + p[i].S) >= ((p[i].F - p[j].F) ^ (p[i].F - p[j].F)); } int ans[maxn]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(); int n; cin >> n; for(int i = 0; i < n; i++){ cin >> p[i].F.F >> p[i].F.S >> p[i].S; arr[i] = i; } sort(arr, arr + n, [](int i, int j){ return (p[i].S == p[j].S ? i > j : p[i].S < p[j].S); } ); for(int i = n-1; i >= 0; i--){ if(ans[ arr[i] ] == 0){ for(int j = i; j >= 0; j--){ if(ans[ arr[j] ] == 0 && ok(arr[i], arr[j])) ans[ arr[j] ] = arr[i] + 1; } } } for(int i = 0; i < n; i++){ cout << ans[i] << " "; } return cout << endl, 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...