oj.uz

Submission #41484

# Submission time Handle Problem Language Result Execution time Memory
41484 2018-02-17T09:33:52 Z Nurlykhan Palembang Bridges (APIO15_bridge) C++14
22 / 100
 120 ms 1664 KB 
    #include <bits/stdc++.h>
     
    #define pii pair<int, int>
    #define f first
    #define s second
    #define pb push_back
    #define mp make_pair
    #define ll long long
    #define ld long double
    #define sz(v) int(v.size())
    #define all(v) v.begin(), v.end()
    #define vec vector<int>
    #define dead not_bad
    #define bad gooood
     
    #define left not_right
    #define y1 what
     
    using namespace std;
     
    const int N = (int) 2e5 + 10;
    const int M = (int) 2e6;
    const ll LINF = (ll) 2e18;
    const int INF = (int) 1e9 + 7;
    const int ALPHA = 26;
    const int mod = INF;
    const double PI = 3.14159265359;
    const ld EPS = (ld) 1e-12;
     
    const int nx[4] = {0, 0, -1, 1};
    const int ny[4] = {1, -1, 0, 0};
     
    vector<int> a, b;
    int k, n;
     
    inline ll get1(int x1, int x2) {
        ll cur = 0;
        for (int i = 0; i < sz(a); i++) {
          int val1, val2;
          if (a[i] <= x1 && x1 <= b[i]) {
            val1 = b[i] - a[i];
          } else if (a[i] > x1) {
            val1 = a[i] + b[i] - 2 * x1;
          } else {
            val1 = 2 * x1 - (a[i] + b[i]);
          }
          if (a[i] <= x2 && x2 <= b[i]) {
            val2 = b[i] - a[i];
          } else if (a[i] > x2) {
            val2 = a[i] + b[i] - 2 * x2;
          } else {
            val2 = 2 * x2 - (a[i] + b[i]);
          }
          cur += min(val1, val2);
        }
        return cur;
    }
     
    ll get(ll x) {
      ll cur = 0;
        for (int i = 0; i < sz(a); i++) {
          if (a[i] <= x && x <= b[i]) {
            cur += b[i] - a[i];
          } else if (a[i] > x) {
            cur += a[i] + b[i] - 2 * x;
          } else if (b[i] < x) {
            cur += 2 * x - (a[i] + b[i]);
          } else {
            assert(0);
          }
        }
        if (k == 2) {
          int l = 0, r = INF;
          while (r - l > 2) {
            int m = (l + r) / 2;
            if (get1(m, x) > get1(m + 1, x)) {
              l = m;
            } else {
              r = m;
            }
          }
          for (ll i = l; i <= r; i++) 
            cur = min(cur, get1(i, x));
        }
        return cur;
    }
     
    ll solve() {
      int l = 0, r = INF;
          while (r - l > 100) {
            int m = (l + r) / 2;
            if (get(m) > get(m + 1)) {
              l = m;
            } else {
              r = m;
            }
          }
      ll ans = LINF;
      for (ll i = l; i <= r; i++) {
        ans = min(ans, get(i));
      }
      return ans + sz(a);
    }
     
    int main() {
      #define fn "teams"
      #ifdef witch
          freopen("input.txt", "r", stdin);
          freopen("output.txt", "w", stdout);
      #else
          //freopen(fn".in", "r", stdin);
          //freopen(fn".out", "w", stdout);
      #endif  
      ll ans = 0;
      cin >> k >> n;
      for (int i = 1; i <= n; i++) {
        char ta, tb;
        int x1, x2;
        scanf("\n%c %d %c %d", &ta, &x1, &tb, &x2);
        //cout << ta << ' ' << x1 << ' ' << tb << ' ' << x2 << endl;
        if (x1 > x2) 
          swap(x1, x2);
        if (ta == tb) {
          ans += x2 - x1;
        } else {
          a.pb(x1);
          b.pb(x2);
        }
      }
      cout << ans + solve();
      return 0;
    }

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:119:51: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("\n%c %d %c %d", &ta, &x1, &tb, &x2);
                                                   ^

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 1 ms 352 KB Output is correct
3 Correct 2 ms 432 KB Output is correct
4 Correct 2 ms 448 KB Output is correct
5 Correct 2 ms 448 KB Output is correct
6 Correct 2 ms 484 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 2 ms 504 KB Output is correct
11 Correct 2 ms 548 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 548 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 2 ms 620 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 2 ms 620 KB Output is correct
7 Correct 2 ms 620 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 2 ms 620 KB Output is correct
10 Correct 2 ms 620 KB Output is correct
11 Correct 3 ms 620 KB Output is correct
12 Correct 64 ms 1564 KB Output is correct
13 Correct 120 ms 1564 KB Output is correct
14 Correct 88 ms 1564 KB Output is correct
15 Correct 72 ms 1564 KB Output is correct
16 Correct 47 ms 1564 KB Output is correct
17 Correct 62 ms 1664 KB Output is correct
18 Correct 61 ms 1664 KB Output is correct
19 Correct 113 ms 1664 KB Output is correct
20 Correct 87 ms 1664 KB Output is correct
21 Correct 116 ms 1664 KB Output is correct

Subtask #3
0 / 9.0

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

Subtask #4
0 / 32.0

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

Subtask #5
0 / 37.0

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