oj.uz

Submission #685180

# Submission time Handle Problem Language Result Execution time Memory
685180 2023-01-23T16:28:40 Z omikron123 Palembang Bridges (APIO15_bridge) C++14
22 / 100
 51 ms 4932 KB 
// https://oj.uz/problem/view/APIO15_bridge

#include <cstdio>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;

// K=1,2, N=1e5
// 1. 家和办公室在同一边的是不参与计算的，和桥没有关系。
// 2. 最小值都在event点上面取得，而且是一个U型的阶梯函数，所以应该可以固定一个桥的位置，然后binary search另外一个。
// 3. 进一步可以发现K=1的时候，答案就是S[i], T[i]的median. 这已经可以得2/3的分了。

int n, K;
ll ans;
vector<pair<int,int>> x;

int main() {
    scanf("%d %d", &K, &n);
    for (int i = 0; i < n; i++) {
        char c1[10], c2[10];
        int x1, x2;
        scanf("%s %d %s %d", c1, &x1, c2, &x2);
        if (c1[0] == c2[0]) ans += abs(x1-x2);
        else x.push_back({min(x1,x2), max(x1,x2)});
    }

    if (K == 1 && x.size()) {
        // just return the median of all numbers
        vector<int> X;
        for (auto p: x) {
            X.push_back(p.first);
            X.push_back(p.second);
        }
        sort(X.begin(), X.end());
        int m = X[X.size() / 2];
        for (auto p: x) {
            ans += abs(p.first-m) + abs(p.second-m) + 1;
        }
    } else {
        
    }

    printf("%lld", ans);

    return 0;
}

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:22:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |     scanf("%d %d", &K, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~
bridge.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         scanf("%s %d %s %d", c1, &x1, c2, &x2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 324 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 292 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 34 ms 3392 KB Output is correct
13 Correct 51 ms 4932 KB Output is correct
14 Correct 49 ms 3648 KB Output is correct
15 Correct 29 ms 2776 KB Output is correct
16 Correct 38 ms 4204 KB Output is correct
17 Correct 41 ms 4880 KB Output is correct
18 Correct 51 ms 4544 KB Output is correct
19 Correct 50 ms 4864 KB Output is correct
20 Correct 38 ms 4484 KB Output is correct
21 Correct 51 ms 4616 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 1 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -