| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 81170 |
2018-10-24T03:27:14 Z |
Hoansn |
Wiring (IOI17_wiring) |
C++14 |
|
90 ms |
69588 KB |
#include <bits/stdc++.h>
#define fi first
#define se second
#define maxn 100007
#define fuck cerr << "Fuck" << '\n';
using namespace std;
typedef long long ll;
typedef pair <int, int> ii;
const int oo = 1e5 + 7;;
int n, m, a[2][maxn];
ll res = 0;
deque <int> f[maxn];
void solve(int id, int n, int m) {
for (int i = 1; i <= n; i++) {
int t = lower_bound(a[!id] + 1, a[!id] + m + 1, a[id][i]) - a[!id];
if (abs(a[id][i] - a[!id][t]) <= abs(a[id][i] - a[!id][t-1])) {
f[t].push_back(i);
}
else f[t-1].push_back(i);
}
for (int i = 1; i<=m; i++) {
if (f[i].size()) continue;
int t = i-1;
while (true) {
if (t == 0 || f[t].size() > 1) break;
t--;
}
int t2 = i+1;
while (true) {
if (t2 == m+1 || f[t2].size() > 1) break;
t2++;
}
int t1;
if (t == 0) t1 = -oo;
else t1 = a[id][f[t].back()];
int t3;
if (t2 == m+1) t3 = -oo;
else t3 = a[id][f[t2].front()];
if (abs(a[!id][i] - t1) <= abs(a[!id][i] - t3)) {
int tmp = f[t].back();
f[i].push_back(tmp);
f[t].pop_back();
}
else {
int tmp = f[t2].front();
f[i].push_back(tmp);
f[t2].pop_front();
}
}
for (int i = 1; i<=m; i++) {
for (int j = 0; j<f[i].size(); j++)
res += abs(a[!id][i] - a[id][f[i][j]]);
}
}
void fuck_solve() {
if (n == m) {
for (int i = 1; i<=n; i++) res -= a[0][i];
for (int i = 1; i<=m; i++) res += a[1][i];
}
if (n > m) {
for (int i = 1; i<=n; i++) res -= a[0][i];
for (int i = 1; i<=m; i++) res += a[1][i];
res += a[1][1] * (n - m);
}
if (n < m) {
for (int i = 1; i<=n; i++) res -= a[0][i];
for (int i = 1; i<=m; i++) res += a[1][i];
res -= a[0][n] * (m - n);
}
}
ll min_total_length(vector <int> r, vector <int> b) {
n = r.size();
m = b.size();
a[0][0] = -oo;
a[1][0] = -oo;
a[0][n+1] = -oo;
a[1][m+1] = -oo;
for (int i = 1; i<=n; i++) a[0][i] = r[i-1]; //cin >> a[0][i];
for (int i = 1; i<=m; i++) a[1][i] = b[i-1]; //cin >> a[1][i];
if (a[0][n] <= a[1][1]) {
fuck_solve();
}
else {
if (n > m) solve(0, n, m);
else solve(1, m, n);
}
return res;
}
/*int main() {
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
freopen("wiring.inp", "r", stdin);
//freopen("wiring.out", "w", stdout);
cin >> n >> m;
a[0][0] = -oo;
a[1][0] = -oo;
a[0][n+1] = -oo;
a[1][m+1] = -oo;
for (int i = 1; i<=n; i++) cin >> a[0][i];
for (int i = 1; i<=m; i++) cin >> a[1][i];
if (a[0][n] <= a[1][1]) {
fuck_solve();
}
else {
if (n > m) solve(0, n, m);
else solve(1, m, n);
}
cout << res;
}*/
Compilation message
wiring.cpp: In function 'void solve(int, int, int)':
wiring.cpp:55:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j<f[i].size(); j++)
~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
67704 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '26187' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
64 ms |
67804 KB |
Output is correct |
| 2 |
Correct |
65 ms |
67804 KB |
Output is correct |
| 3 |
Incorrect |
90 ms |
69588 KB |
3rd lines differ - on the 1st token, expected: '41596985758595', found: '8388298625923' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
69588 KB |
Output is correct |
| 2 |
Incorrect |
66 ms |
69588 KB |
3rd lines differ - on the 1st token, expected: '17703', found: '19704' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
68 ms |
69588 KB |
3rd lines differ - on the 1st token, expected: '27', found: '32' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
67704 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '26187' |
| 2 |
Halted |
0 ms |
0 KB |
- |
