oj.uz

Submission #60526

# Submission time Handle Problem Language Result Execution time Memory
60526 2018-07-24T10:00:40 Z Flugan42 Palembang Bridges (APIO15_bridge) C++14
0 / 100
 5 ms 852 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

typedef long long ll;
typedef long double lld;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;

#define rep(i, from, to) for(int i = from; i < to; i++)
#define inf 1000000000000000000

int main(){
  char a,b; ll n,c,d,k,s = 0,s1 = 0;
  cin >> k >> n;
  vi Q;
  rep(i, 0, n){
    cin >> a >> c >> b >> d;
    if (a == b) s += abs(d-c);
    else { Q.push_back(c); Q.push_back(d); }
  }
  sort(Q.begin(), Q.end());
  rep(i, 0, Q.size()) cout << Q[i] << " "; cout << endl;
  s += Q.size()/2;
  if (k == 1) rep(i, 0, Q.size()) s += abs(Q[i]-Q[Q.size()/2]);
  else {
    vi d1, d2;
    d1.assign(Q.size(), 0);
    d2.assign(Q.size(), 0);
    d1[0] = 0; d2.back() = 0;
    rep(i, 1, Q.size()){
      d1[i] = d1[i-1]+Q[i]-Q[0];
      d2[Q.size()-i-1] = d2[Q.size()-i]+Q.back()-Q[Q.size()-i-1];
    }
    rep(i,0,Q.size()) cout << d1[i] << " " << d2[i] << endl;
    s1 = inf;
    rep(i, 0, Q.size()-1){
      ll temp = 0; ll b1 = i/2, b2 = (Q.size()+i)/2;
      temp += d1[i]-d1[b1];
      temp -= (Q[b1]-Q[0])*(i-b1);
      temp += d1.back()-d1[b2];
      temp -= (Q[b2]-Q[0])*(Q.size()-b2-1);

      temp += d2[0]-d2[b1];
      temp -= (Q.back()-Q[b1])*b1;
      temp += d2[i+1]-d2[b2];
      temp -= (Q.back()-Q[b2])*(b2-i-1);
      cout << i << " " << temp << " " << s1 << endl;
      s1 = min(temp, s1);
    }
  }
  cout << s+s1 << endl;
}

/*
0 1 2 3 4 5 6 7 8 9 10   11 12 13 14 15 16
0 1 2 3 4 5 6 7 8 9   10 11 12 13 14 15 16
*/

Compilation message

bridge.cpp: In function 'int main()':
bridge.cpp:13:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, from, to) for(int i = from; i < to; i++)
bridge.cpp:26:7:
   rep(i, 0, Q.size()) cout << Q[i] << " "; cout << endl;
       ~~~~~~~~~~~~~~                          
bridge.cpp:26:3: note: in expansion of macro 'rep'
   rep(i, 0, Q.size()) cout << Q[i] << " "; cout << endl;
   ^~~
bridge.cpp:13:26: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define rep(i, from, to) for(int i = from; i < to; i++)
                          ^
bridge.cpp:26:3: note: in expansion of macro 'rep'
   rep(i, 0, Q.size()) cout << Q[i] << " "; cout << endl;
   ^~~
bridge.cpp:26:44: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   rep(i, 0, Q.size()) cout << Q[i] << " "; cout << endl;
                                            ^~~~
bridge.cpp:13:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, from, to) for(int i = from; i < to; i++)
bridge.cpp:28:19:
   if (k == 1) rep(i, 0, Q.size()) s += abs(Q[i]-Q[Q.size()/2]);
                   ~~~~~~~~~~~~~~              
bridge.cpp:28:15: note: in expansion of macro 'rep'
   if (k == 1) rep(i, 0, Q.size()) s += abs(Q[i]-Q[Q.size()/2]);
               ^~~
bridge.cpp:13:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, from, to) for(int i = from; i < to; i++)
bridge.cpp:34:9:
     rep(i, 1, Q.size()){
         ~~~~~~~~~~~~~~                        
bridge.cpp:34:5: note: in expansion of macro 'rep'
     rep(i, 1, Q.size()){
     ^~~
bridge.cpp:13:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, from, to) for(int i = from; i < to; i++)
bridge.cpp:38:9:
     rep(i,0,Q.size()) cout << d1[i] << " " << d2[i] << endl;
         ~~~~~~~~~~~~                          
bridge.cpp:38:5: note: in expansion of macro 'rep'
     rep(i,0,Q.size()) cout << d1[i] << " " << d2[i] << endl;
     ^~~
bridge.cpp:13:46: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define rep(i, from, to) for(int i = from; i < to; i++)
bridge.cpp:40:9:
     rep(i, 0, Q.size()-1){
         ~~~~~~~~~~~~~~~~                      
bridge.cpp:40:5: note: in expansion of macro 'rep'
     rep(i, 0, Q.size()-1){
     ^~~

Subtask #1
0 / 8.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 796 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 32.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 852 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -