Submission #1690948
Source Code Expand
#include <bits/stdc++.h> #define mp make_pair #define pb push_back #define IOS ios::sync_with_stdio(false); cin.tie(0); #define sd(n) scanf("%d",&n) #define sl(n) scanf("%lld",&n) #define pd(n) printf("%d",n) #define pl(n) printf("%lld",n) #define sf(n) scanf("%Lf",&n) #define pf(n) printf("%.12Lf",n) #define psp printf(" ") #define endc printf("\n") using namespace std; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; const int maxn = 4e4 + 600; const ld eps = 1e-10; const ld LIM = 3e8; ld a[maxn]; ld b[maxn]; ld c[maxn]; int occ[maxn]; int n; ld sep; int bit[maxn]; bool sepsort(int i,int j) { return ((c[i] - a[i]*sep)/b[i]) < ((c[j] - a[j]*sep)/b[j]); } vector<int> getseq(ld z) { sep = z; vector<int> ans; for (int i = 1; i <= n; i++) ans.pb(i); sort(ans.begin(), ans.end(), sepsort); return ans; } void upd(int x) { while (x < maxn) { bit[x]++; x += x & (-x); } } int qry(int x) { int ans = 0; while (x > 0) { ans += bit[x]; x -= x & (-x); } return ans; } int inv(vector<int> A) { for (int i = 0; i < n; i++) A[i] = occ[A[i]]; fill(bit, bit + maxn, 0); int ans = 0; for (int i = n - 1 ; i >= 0; i--) { ans += qry(A[i]); upd(A[i]); } return ans; } ld solve() { int C = (n * (n - 1)/2)/2; vector<int> S = getseq(LIM), Q; for (int i = 0; i < n; i++) occ[S[i]] = i + 1; ld l = -LIM, r = LIM; while (r - l > eps) { ld mid = (l + r)/2; Q = getseq(mid); int z = inv(Q); if (z > C) l = mid; else r = mid; } return (l + r)/2; } int main() { sd(n); for (int i = 1; i <= n; i++) { sf(a[i]); sf(b[i]); sf(c[i]); } ld mx = solve(); for (int i = 1; i <= n; i++) swap(a[i], b[i]); ld my = solve(); cout<<setprecision(12)<<mx<<" "<<my<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - CARtesian Coodinate |
User | mbrc |
Language | C++14 (GCC 5.4.1) |
Score | 800 |
Code Size | 1839 Byte |
Status | AC |
Exec Time | 1936 ms |
Memory | 3228 KB |
Compile Error
./Main.cpp: In function ‘int main()’: ./Main.cpp:85:7: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] sd(n); ^ ./Main.cpp:87:11: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] sf(a[i]); sf(b[i]); sf(c[i]); ^ ./Main.cpp:87:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] sf(a[i]); sf(b[i]); sf(c[i]); ^ ./Main.cpp:87:31: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result] sf(a[i]); sf(b[i]); sf(c[i]); ^
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 800 / 800 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | s1.txt, s2.txt, s3.txt |
All | 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, s1.txt, s2.txt, s3.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01.txt | AC | 1892 ms | 3228 KB |
02.txt | AC | 1884 ms | 3228 KB |
03.txt | AC | 1902 ms | 3228 KB |
04.txt | AC | 1887 ms | 3228 KB |
05.txt | AC | 1936 ms | 3228 KB |
06.txt | AC | 1887 ms | 3228 KB |
07.txt | AC | 1882 ms | 3228 KB |
08.txt | AC | 1886 ms | 3228 KB |
09.txt | AC | 1889 ms | 3228 KB |
10.txt | AC | 1894 ms | 3228 KB |
11.txt | AC | 1887 ms | 3228 KB |
12.txt | AC | 1893 ms | 3228 KB |
13.txt | AC | 1883 ms | 3228 KB |
14.txt | AC | 1897 ms | 3228 KB |
15.txt | AC | 1912 ms | 3228 KB |
16.txt | AC | 1886 ms | 3228 KB |
17.txt | AC | 1913 ms | 3228 KB |
18.txt | AC | 1901 ms | 3228 KB |
19.txt | AC | 1895 ms | 3228 KB |
20.txt | AC | 1901 ms | 3228 KB |
21.txt | AC | 1836 ms | 3228 KB |
22.txt | AC | 1818 ms | 3228 KB |
23.txt | AC | 1858 ms | 3228 KB |
24.txt | AC | 1874 ms | 3228 KB |
25.txt | AC | 1861 ms | 3228 KB |
26.txt | AC | 1862 ms | 3228 KB |
27.txt | AC | 3 ms | 384 KB |
28.txt | AC | 3 ms | 384 KB |
29.txt | AC | 3 ms | 384 KB |
30.txt | AC | 3 ms | 384 KB |
31.txt | AC | 3 ms | 384 KB |
32.txt | AC | 3 ms | 384 KB |
s1.txt | AC | 3 ms | 384 KB |
s2.txt | AC | 3 ms | 384 KB |
s3.txt | AC | 3 ms | 384 KB |