QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#788945#9738. Make It DivisibleshinonomezhouWA 0ms3612kbC++141.7kb2024-11-27 18:50:522024-11-27 18:50:52

Judging History

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

  • [2024-11-27 18:50:52]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3612kb
  • [2024-11-27 18:50:52]
  • 提交

answer

#include <bits/stdc++.h>
#include <cmath>

// #define x first
// #define y second

using namespace std;

typedef double ld;
typedef unsigned long ul;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;

const int maxn = 2e6 + 50;
const ll inf = 0x3f3f3f3f3f3f;
const vector<pll> dxy = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

ll b[maxn];

struct P {
  ll x, y;
  bool operator<(const P &p) const { return x - y < p.x - p.y; }
};

void solve() {
  ll n, k;
  cin >> n >> k;
  for (ll i = 1; i <= n; i++) {
    cin >> b[i];
  }
  if (n == 1) {
    cout << k << ' ' << (k + 1) * k / 2 << '\n';
    return;
  }
  set<P> st;
  ll tpi = -1;
  for (ll i = 1; i <= n; i++) {
    if (i == 1) {
      tpi = 1;
    } else {
      if (b[i] < b[tpi]) {
        st.insert({b[tpi], b[i]});
        tpi = i;
      }
    }
  }
  tpi = -1;
  for (ll i = n; i >= 1; i--) {
    if (i == n) {
      tpi = n;
    } else {
      if (b[i] < b[tpi]) {
        st.insert({b[tpi], b[i]});
        tpi = i;
      }
    }
  }
  set<ll> ans;
  P pr = *st.begin();
  ll di = pr.x - pr.y;
  for (ll ki = 2; 2 * (ki - 1) <= di && di <= k * (ki - 1); ki++) {
    if (di % (ki - 1) != 0)
      continue;
    ll x = di / (ki - 1) - 1;
    if (x < 1 || x > k)
      continue;
    for (auto i : st) {
      if ((i.x + x) % (i.y + x) == 0) {
        ans.insert(x);
      }
    }
  }

  ll res = 0ll;
  for (auto i : ans) {
    res += i;
  }
  cout << ans.size() << ' ' << res << '\n';
}

void init() {
  // init_primes();
}

int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  init();
  int _t = 1;
  cin >> _t;
  cin.get();
  while (_t--)
    solve();

  return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3612kb

input:

3
5 10
7 79 1 7 1
2 1000000000
1 2
1 100
1000000000

output:

3 8
0 0
100 5050

result:

ok 3 lines

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3496kb

input:

4
201 1000000000
1 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5 2 5...

output:

0 0
2 4
0 0
0 0

result:

wrong answer 2nd lines differ - expected: '0 0', found: '2 4'