| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 49066 |
2018-05-21T17:24:10 Z |
Namnamseo |
Wiring (IOI17_wiring) |
C++17 |
|
75 ms |
6732 KB |
#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pp=pair<int,int>;
#define x first
#define y second
#define DBG if(0)
int n, m;
int pn;
pp pt[200010];
int sz[2];
int plst[2][100010];
int con[2][100010];
int aite[2][100010];
int wait[2][100010];
void build_pt(vector<int>& r, vector<int>& b){
sz[0] = n = r.size();
sz[1] = m = b.size();
for(int i=0; i<n; ++i) plst[0][i]=r[i];
for(int i=0; i<m; ++i) plst[1][i]=b[i];
for(int ri=0; ri<2; ++ri){
fill(con[ri], con[ri]+sz[ri], 0);
fill(wait[ri], wait[ri]+sz[ri], 0);
}
for(int i=0, j=0; i<n || j<m;){
if(i<n && (j==m || r[i]<b[j])){
pt[pn].x = r[i];
pt[pn].y = i;
++pn; ++i;
} else {
pt[pn].x = b[j];
pt[pn].y = n+j;
++pn; ++j;
}
}
}
ll ans;
void connect1(int ri, bool force){
int ss = sz[ri];
for(int i=0; i<ss; ++i) if(!wait[ri][i] && !con[ri][i]){
int mp = plst[ri][i];
int jnxt = lower_bound(plst[ri^1], plst[ri^1]+sz[ri^1], mp) - plst[ri^1];
int jbef = jnxt-1;
int dnxt = (0<=jnxt && jnxt<sz[ri^1] ? abs(plst[ri^1][jnxt]-mp) : 2e9);
int dbef = (0<=jbef && jbef<sz[ri^1] ? abs(plst[ri^1][jbef]-mp) : 2e9);
if(dnxt == dbef){
if(force){
++con[ri][i]; aite[ri][i]=jbef;
++con[ri^1][jbef]; aite[ri^1][jbef]=i;
ans += dbef;
DBG printf("c1%d %d,%d - %d,%d ### cost %3d\n", force, ri, i, ri^1, jbef, dbef);
}
} else if(dnxt > dbef){
++con[ri][i]; aite[ri][i]=jbef;
++con[ri^1][jbef]; aite[ri^1][jbef]=i;
ans += dbef;
DBG printf("c1%d %d,%d - %d,%d ### cost %3d\n", force, ri, i, ri^1, jbef, dbef);
} else {
++con[ri][i]; aite[ri][i]=jnxt;
++con[ri^1][jnxt]; aite[ri^1][jnxt]=i;
ans += dnxt;
DBG printf("c1%d %d,%d - %d,%d ### cost %3d\n", force, ri, i, ri^1, jnxt, dnxt);
}
}
}
void connect2(int ri){
int ss = sz[ri];
for(int i=0; i<ss; ++i) if(wait[ri][i] && !con[ri][i]){
int mp = plst[ri][i];
int jnxt = lower_bound(plst[ri^1], plst[ri^1]+sz[ri^1], mp) - plst[ri^1];
int jbef = jnxt-1;
int dnxt = (0<=jnxt && jnxt<sz[ri^1] ? abs(plst[ri^1][jnxt]-mp) : 2e9);
int dbef = (0<=jbef && jbef<sz[ri^1] ? abs(plst[ri^1][jbef]-mp) : 2e9);
if(con[ri^1][jnxt] == 1 && con[ri][aite[ri^1][jnxt]] >= 2){
dnxt -= abs(plst[ri][aite[ri^1][jnxt]]-plst[ri^1][jnxt]);
}
if(con[ri^1][jbef] == 1 && con[ri][aite[ri^1][jbef]] >= 2){
dbef -= abs(plst[ri][aite[ri^1][jbef]]-plst[ri^1][jbef]);
}
if(dnxt >= dbef){
++con[ri][i]; aite[ri][i]=jbef;
++con[ri^1][jbef]; aite[ri^1][jbef]=i;
ans += dbef;
DBG printf("c2n %d,%d - %d,%d ### cost %3d\n", ri, i, ri^1, jbef, dbef);
} else {
++con[ri][i]; aite[ri][i]=jnxt;
++con[ri^1][jnxt]; aite[ri^1][jnxt]=i;
ans += dnxt;
DBG printf("c2n %d,%d - %d,%d ### cost %3d\n", ri, i, ri^1, jnxt, dnxt);
}
}
}
ll min_total_length(vector<int> r, vector<int> b) {
build_pt(r, b);
ans = 0;
for(int i=2, p1=(pt[0].y>=n), p2=(pt[1].y>=n); i<pn; ++i){
int p3=(pt[i].y>=n);
if(p1==p2 && p2==p3){
wait[p2][pt[i-1].y-p2*n] = 1;
}
p1=p2; p2=p3;
}
connect1(0, 0);
connect1(1, 0);
connect1(0, 1);
connect1(1, 1);
connect2(0);
connect2(1);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '37630' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
488 KB |
3rd lines differ - on the 1st token, expected: '904', found: '946' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
524 KB |
3rd lines differ - on the 1st token, expected: '316', found: '356' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
524 KB |
Output is correct |
| 2 |
Incorrect |
75 ms |
6732 KB |
3rd lines differ - on the 1st token, expected: '373710605', found: '373776928' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
376 KB |
3rd lines differ - on the 1st token, expected: '25859', found: '37630' |
| 2 |
Halted |
0 ms |
0 KB |
- |
