QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#164830#7184. Transport Plusesucup-team087#WA 1ms3724kbC++143.0kb2023-09-05 13:56:582023-09-05 13:56:58

Judging History

你现在查看的是最新测评结果

  • [2023-09-05 13:56:58]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3724kb
  • [2023-09-05 13:56:58]
  • 提交

answer

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")


constexpr double INF = 1e+12;
double sq(double r) { return r * r; }

int N;
Int T;
vector<Int> X, Y;

int main() {
  for (; ~scanf("%d%lld", &N, &T); ) {
    X.resize(N + 2);
    Y.resize(N + 2);
    for (int i = 0; i < N + 2; ++i) {
      scanf("%lld%lld", &X[i], &Y[i]);
    }
    
    Int dist[2][110] = {};
    pair<Int, Int> nearest[2][110] = {};
    for (int i = 0; i < 2; ++i) for (int j = 2; j < N + 2; ++j) {
      dist[i][j] = INF;
      if (chmin(dist[i][j], abs(X[j] - X[i]))) nearest[i][j] = make_pair(X[j], Y[i]);
      if (chmin(dist[i][j], abs(Y[j] - Y[i]))) nearest[i][j] = make_pair(X[i], Y[j]);
    }
    
    double ans = INF;
    vector<pair<int, pair<Int, Int>>> ops;
    
    // 0
    {
      if (chmin(ans, sq(X[1] - X[0]) + sq(Y[1] - Y[0]))) {
        ops.clear();
        ops.emplace_back(-1, make_pair(X[1], Y[1]));
      }
    }
    
    // 1
    for (int i = 2; i < N + 2; ++i) {
      if (chmin<double>(ans, dist[0][i] + T + dist[1][i])) {
        ops.clear();
        ops.emplace_back(-1, nearest[0][i]);
        ops.emplace_back(i, nearest[1][i]);
        ops.emplace_back(-1, make_pair(X[1], Y[1]));
      }
    }
    
    // 2
    for (int i = 2; i < N + 2; ++i) for (int j = 2; j < N + 2; ++j) {
      if (chmin<double>(ans, dist[0][i] + T + T + dist[1][j])) {
        ops.clear();
        ops.emplace_back(-1, nearest[0][i]);
        ops.emplace_back(i, make_pair(X[j], Y[i]));
        ops.emplace_back(j, nearest[1][j]);
        ops.emplace_back(-1, make_pair(X[1], Y[1]));
      }
    }
    
    printf("%.12f\n", ans);
    printf("%d\n", (int)ops.size());
    for (const auto &op : ops) {
      printf("%d %lld %lld\n", max(op.first - 1, 0), op.second.first, op.second.second);
    }
  }
  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3700kb

input:

1 2
1 1
5 3
6 2

output:

4.000000000000
3
0 1 2
1 6 3
0 5 3

result:

ok correct

Test #2:

score: 0
Accepted
time: 1ms
memory: 3724kb

input:

2 1
1 1
6 1
1 3
6 3

output:

2.000000000000
4
0 1 1
1 6 3
2 6 1
0 6 1

result:

ok correct

Test #3:

score: 0
Accepted
time: 0ms
memory: 3688kb

input:

0 0
1 1
1 1

output:

0.000000000000
1
0 1 1

result:

ok correct

Test #4:

score: -100
Wrong Answer
time: 1ms
memory: 3692kb

input:

0 0
100 100
0 0

output:

20000.000000000000
1
0 0 0

result:

wrong answer claimed 20000.0000000000, actual 141.4213562373