QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#270287#7753. Energy Distributionucup-team859#WA 902ms3980kbC++143.0kb2023-11-30 18:08:532023-11-30 18:08:54

Judging History

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

  • [2024-10-31 10:22:30]
  • hack成功,自动添加数据
  • (/hack/1089)
  • [2023-11-30 18:08:54]
  • 评测
  • 测评结果:WA
  • 用时:902ms
  • 内存:3980kb
  • [2023-11-30 18:08:53]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
using namespace chrono;

using ll = long long;
using ull = unsigned long long;

string to_string(const string &s) {
  return '"' + s + '"';
}

string to_string(bool b) {
  return b ? "true" : "false";
}

template <typename A, typename B>
string to_string(const pair<A, B> &p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename T>
string to_string(const T &v) {
  string s = "{";
  bool first = true;
  for (const auto &it : v) {
    if (!first)
      s += ", ";
    else
      first = false;
    s += to_string(it);
  }
  return s += "}";
}

void debug_out() {
  cerr << endl;
}

template <typename T, typename... Args>
void debug_out(const T &first, const Args&... rest) {
  cerr << to_string(first) << " ";
  debug_out(rest...);
}

#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

auto startTime = high_resolution_clock::now();
int get_time() {
  auto stopTime = chrono::high_resolution_clock::now();
  auto duration = duration_cast<milliseconds>(stopTime - startTime);
  return duration.count(); // in ms
}

using ld = long double;

const ld eps = 1e-1;
const ld lim_step = 1e-12;

int n;
int w[11][11];

ld eval(vector<ld> &p) {
  ld sum = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = i + 1; j <= n; ++j)
      sum += p[i] * p[j] * w[i][j];
  }

  return sum;
}

void norm(vector<ld> &p) {
  ld sum = 0;
  for (int i = 1; i <= n; ++i)
    sum += p[i];

  for (int i = 1; i <= n; ++i)
    p[i] /= sum;
}

ld run_regr(vector<ld> &p, ld step = eps) {
  while (get_time() <= 950) {
    ld best = eval(p), df;
    int pos = -1;
    vector<ld> aux = p;
    for (int i = 1; i <= n; ++i) {
      p[i] += eps;
      norm(p);
      ld res = eval(p);
      if (res > best) {
        best = res;
        df = eps;
        pos = i;
      }
      p = aux;

      p[i] -= eps;
      if (p[i] >= 0) {
        norm(p);
        ld res = eval(p);
        if (res > best) {
          best = res;
          df = -eps;
          pos = i;
        }
      }
      p = aux;
    }

    if (pos == -1) {
      step /= 2;
      if (step < lim_step)
        return best;
      continue;
    }

    p[pos] += df;
    norm(p);
  }

  return eval(p);
}

void solve() {
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      cin >> w[i][j];
    }
  }

  vector<ld> p(n + 1, 0);
  ld best = 0;
  while (get_time() <= 900) {
    auto dis = uniform_real_distribution<ld>(0, 1);
    for (int i = 1; i <= n; ++i)
      p[i] = dis(rng);

    norm(p);
    best = max(best, run_regr(p));
  }
  cout << fixed << setprecision(20) << best << "\n";
}

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false);

  int t = 1;
//  cin >> t;
  while (t--)
    solve();

  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 898ms
memory: 3976kb

input:

2
0 1
1 0

output:

0.24999999999999133363

result:

ok found '0.2500000', expected '0.2500000', error '0.0000000'

Test #2:

score: 0
Accepted
time: 901ms
memory: 3980kb

input:

3
0 2 1
2 0 2
1 2 0

output:

0.57142856731288661450

result:

ok found '0.5714286', expected '0.5714290', error '0.0000004'

Test #3:

score: 0
Accepted
time: 901ms
memory: 3860kb

input:

3
0 1 2
1 0 1
2 1 0

output:

0.49999996833286479872

result:

ok found '0.5000000', expected '0.5000000', error '0.0000000'

Test #4:

score: -100
Wrong Answer
time: 902ms
memory: 3844kb

input:

4
0 3 1 0
3 0 1 0
1 1 0 2
0 0 2 0

output:

0.74895502706552185971

result:

wrong answer 1st numbers differ - expected: '0.7500000', found: '0.7489550', error = '0.0010450'