QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#431014 | #8676. Three Kinds of Dice | quack | Compile Error | / | / | C++14 | 4.3kb | 2024-06-04 20:08:38 | 2024-06-04 20:08:39 |
Judging History
answer
#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
int n, m, tot, w[400010];
vector<int> a, b, c;
vector<pii> pt, st;
int query(const vector<int> &v, int x) {
auto it1 = lower_bound(v.begin(), v.end(), x);
auto it2 = upper_bound(v.begin(), v.end(), x);
int ans1 = it1 - v.begin(), ans2 = it2 - it1;
return ans1 * 2 + ans2;
}
bool check(pii u, pii v, pii w) {
return 1ll * (w.second - v.second) * (v.first - u.first) <= 1ll * (v.second - u.second) * (w.first - v.first);
}
int main() {
scanf("%d", &n);
for (int i = 0, x; i < n; ++i) scanf("%d", &x), a.push_back(x), c.push_back(x);
scanf("%d", &m);
for (int i = 0, x; i < m; ++i) scanf("%d", &x), b.push_back(x), c.push_back(x);
c.push_back(1);
sort(a.begin(), a.end());
sort(b.begin(), b.end());
long long tot = 0;
for (int x : a) tot += query(b, x);
if (tot < 1ll * n * m) {
swap(n, m);
swap(a, b);
}
sort(c.begin(), c.end());
auto last = unique(c.begin(), c.end());
c.erase(last, c.end());
c.push_back(1e9 + 2);
for (int i = 0; i < c.size() - 1; ++i) {
pt.push_back(pii(query(a, c[i]), query(b, c[i])));
if (c[i] + 1 < c[i+1])
pt.push_back(pii(query(a, (c[i] + c[i+1]) / 2), query(b, (c[i] + c[i+1]) / 2)));
}
sort(pt.begin(), pt.end());
for (pii p : pt) {
while(st.size() > 1 && check(st[st.size()-2], st[st.size()-1], p)) st.pop_back();
st.push_back(p);
}
double ans1, ans2;
int k = lower_bound(st.begin(), st.end(), pii(n, 0)) - st.begin();
if (st[k].first == n) ans1 = 0.5 * st[k].second / m;
else ans1 = (1.0 * (st[k].second - st[k-1].second) / (st[k].first - st[k-1].first) * (n - st[k-1].first) + st[k-1].second) / 2 / m;
k = lower_bound(st.begin(), st.end(), pii(0, m), [](pii x, pii y){return x.second == y.second ? x.first < y.first : x.second < y.second;}) - st.begin();
if (st[k].second == m) ans2 = 0.5 * st[k].first / n;
else ans2 = (1.0 * (st[k].first - st[k-1].first) / (st[k].second - st[k-1].second) * (m - st[k-1].second) + st[k-1].first) / 2 / n;
printf("%lf %lf\n", ans1, ans2);
}#include <bits/stdc++.h>
#define pii pair<int, int>
using namespace std;
int n, m, tot, w[400010];
vector<int> a, b, c;
vector<pii> pt, st;
int query(const vector<int> &v, int x) {
auto it1 = lower_bound(v.begin(), v.end(), x);
auto it2 = upper_bound(v.begin(), v.end(), x);
int ans1 = it1 - v.begin(), ans2 = it2 - it1;
return ans1 * 2 + ans2;
}
bool check(pii u, pii v, pii w) {
return 1ll * (w.second - v.second) * (v.first - u.first) <= 1ll * (v.second - u.second) * (w.first - v.first);
}
int main() {
scanf("%d", &n);
for (int i = 0, x; i < n; ++i) scanf("%d", &x), a.push_back(x), c.push_back(x);
scanf("%d", &m);
for (int i = 0, x; i < m; ++i) scanf("%d", &x), b.push_back(x), c.push_back(x);
c.push_back(1);
sort(a.begin(), a.end());
sort(b.begin(), b.end());
long long tot = 0;
for (int x : a) tot += query(b, x);
if (tot < 1ll * n * m) {
swap(n, m);
swap(a, b);
}
sort(c.begin(), c.end());
auto last = unique(c.begin(), c.end());
c.erase(last, c.end());
c.push_back(1e9 + 2);
for (int i = 0; i < c.size() - 1; ++i) {
pt.push_back(pii(query(a, c[i]), query(b, c[i])));
if (c[i] + 1 < c[i+1])
pt.push_back(pii(query(a, (c[i] + c[i+1]) / 2), query(b, (c[i] + c[i+1]) / 2)));
}
sort(pt.begin(), pt.end());
for (pii p : pt) {
while(st.size() > 1 && check(st[st.size()-2], st[st.size()-1], p)) st.pop_back();
st.push_back(p);
}
double ans1, ans2;
int k = lower_bound(st.begin(), st.end(), pii(n, 0)) - st.begin();
if (st[k].first == n) ans1 = 0.5 * st[k].second / m;
else ans1 = (1.0 * (st[k].second - st[k-1].second) / (st[k].first - st[k-1].first) * (n - st[k-1].first) + st[k-1].second) / 2 / m;
k = lower_bound(st.begin(), st.end(), pii(0, m), [](pii x, pii y){return x.second == y.second ? x.first < y.first : x.second < y.second;}) - st.begin();
if (st[k].second == m) ans2 = 0.5 * st[k].first / n;
else ans2 = (1.0 * (st[k].first - st[k-1].first) / (st[k].second - st[k-1].second) * (m - st[k-1].second) + st[k-1].first) / 2 / n;
printf("%lf %lf\n", ans1, ans2);
}
Details
answer.code:52:2: error: stray ‘#’ in program 52 | }#include <bits/stdc++.h> | ^ answer.code:52:3: error: ‘include’ does not name a type 52 | }#include <bits/stdc++.h> | ^~~~~~~ answer.code:55:5: error: redefinition of ‘int n’ 55 | int n, m, tot, w[400010]; | ^ answer.code:4:5: note: ‘int n’ previously declared here 4 | int n, m, tot, w[400010]; | ^ answer.code:55:8: error: redefinition of ‘int m’ 55 | int n, m, tot, w[400010]; | ^ answer.code:4:8: note: ‘int m’ previously declared here 4 | int n, m, tot, w[400010]; | ^ answer.code:55:11: error: redefinition of ‘int tot’ 55 | int n, m, tot, w[400010]; | ^~~ answer.code:4:11: note: ‘int tot’ previously declared here 4 | int n, m, tot, w[400010]; | ^~~ answer.code:55:16: error: redefinition of ‘int w [400010]’ 55 | int n, m, tot, w[400010]; | ^ answer.code:4:16: note: ‘int w [400010]’ previously declared here 4 | int n, m, tot, w[400010]; | ^ answer.code:56:13: error: redefinition of ‘std::vector<int> a’ 56 | vector<int> a, b, c; | ^ answer.code:5:13: note: ‘std::vector<int> a’ previously declared here 5 | vector<int> a, b, c; | ^ answer.code:56:16: error: redefinition of ‘std::vector<int> b’ 56 | vector<int> a, b, c; | ^ answer.code:5:16: note: ‘std::vector<int> b’ previously declared here 5 | vector<int> a, b, c; | ^ answer.code:56:19: error: redefinition of ‘std::vector<int> c’ 56 | vector<int> a, b, c; | ^ answer.code:5:19: note: ‘std::vector<int> c’ previously declared here 5 | vector<int> a, b, c; | ^ answer.code:57:13: error: redefinition of ‘std::vector<std::pair<int, int> > pt’ 57 | vector<pii> pt, st; | ^~ answer.code:6:13: note: ‘std::vector<std::pair<int, int> > pt’ previously declared here 6 | vector<pii> pt, st; | ^~ answer.code:57:17: error: redefinition of ‘std::vector<std::pair<int, int> > st’ 57 | vector<pii> pt, st; | ^~ answer.code:6:17: note: ‘std::vector<std::pair<int, int> > st’ previously declared here 6 | vector<pii> pt, st; | ^~ answer.code:58:5: error: redefinition of ‘int query(const std::vector<int>&, int)’ 58 | int query(const vector<int> &v, int x) { | ^~~~~ answer.code:7:5: note: ‘int query(const std::vector<int>&, int)’ previously defined here 7 | int query(const vector<int> &v, int x) { | ^~~~~ answer.code:64:6: error: redefinition of ‘bool check(std::pair<int, int>, std::pair<int, int>, std::pair<int, int>)’ 64 | bool check(pii u, pii v, pii w) { | ^~~~~ answer.code:13:6: note: ‘bool check(std::pair<int, int>, std::pair<int, int>, std::pair<int, int>)’ previously defined here 13 | bool check(pii u, pii v, pii w) { | ^~~~~ answer.code:67:5: error: redefinition of ‘int main()’ 67 | int main() { | ^~~~ answer.code:16:5: note: ‘int main()’ previously defined here 16 | int main() { | ^~~~ answer.code: In function ‘int main()’: answer.code:17:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 17 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ answer.code:18:41: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 18 | for (int i = 0, x; i < n; ++i) scanf("%d", &x), a.push_back(x), c.push_back(x); | ~~~~~^~~~~~~~~~ answer.code:19:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 19 | scanf("%d", &m); | ~~~~~^~~~~~~~~~ answer.code:20:41: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 20 | for (int i = 0, x; i < m; ++i) scanf("%d", &x), b.push_back(x), c.push_back(x); | ~~~~~^~~~~~~~~~ answer.code: In function ‘int main()’: answer.code:68:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 68 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ answer.code:69:41: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 69 | for (int i = 0, x; i < n; ++i) scanf("%d", &x), a.push_back(x), c.push_back(x); | ~~~~~^~~~~~~~~~ answer.code:70:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 70 | scanf("%d", &m); | ~~~~~^~~~~~~~~~ answer.code:7...