QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#205177#7560. Computer Networkucup-team859#WA 0ms3812kbC++232.9kb2023-10-07 15:05:462023-10-07 15:05:46

Judging History

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

  • [2023-10-07 15:05:46]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3812kb
  • [2023-10-07 15:05:46]
  • 提交

answer

#include <bits/stdc++.h>

#define lsb(x) (x & (-x))

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

using namespace std;
using namespace chrono;

int ans = -1;
auto startTime = high_resolution_clock::now();

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void back(vector<int> &a, const vector<int> &b, int h = 0) {
  auto stopTime = chrono::high_resolution_clock::now();
  auto duration = duration_cast<milliseconds>(stopTime - startTime);
  if (duration.count() >= 950) {
    cout << ans << endl;
    exit(0);
  }

  int n = (int)a.size();
  int df = b[0] - a[0], mx = b[0] - a[0];
  for (int i = 1; i < a.size(); ++i) {
    if (b[i] - a[i] != df)
      df = -1;
    mx = max(b[i] - a[i], mx);

    if (a[i] - a[i - 1] < b[i] - b[i - 1])
      return;
  }

  /**for (int i = 0; i < n; ++i)
    cout << a[i] << " ";
  cout << endl;
  **/

  if (df >= 0) {
    if (ans == -1)
      ans = h + df;
    else ans = min(ans, h + df);
    cout << ans << endl;
    exit(0);

    return;
  }

  if (ans != -1 && h + mx > ans)
    return;
    //;

  vector<int> aux_a = a;

  //if (rng() & 1) {
    for (int i = 0; i < n; ++i) {
      a[i] /= 2;
    }

    back(a, b, h + 1);
    

    a = aux_a;
    for (int i = 0; i < n; ++i) {
      a[i] = (a[i] + 1) / 2;
    }

    back(a, b, h + 2);
  /**} else {
    for (int i = 0; i < n; ++i) {
      a[i] /= 2;
    }

    back(a, b, h + 1);
    

    a = aux_a;
    for (int i = 0; i < n; ++i) {
      a[i] = (a[i] + 1) / 2;
    }

    back(a, b, h + 2);
  }**/
}

void solve() {
  int n;
  cin >> n;
  vector<int> a(n), b(n);
  vector<pair<int, int>> a1;
  vector<int> b1;
  for (int i = 0; i < n; ++i)
    cin >> a[i];
  

  for (int i = 0; i < n; ++i)
    cin >> b[i];

  /**
  for (int i = 0; i < n; ++i) {
    a1.push_back({a[i], i});
  }

  b1 = b;
  sort(a1.begin(), a1.end());
  sort(b1.begin(), b1.end());

  vector<int> b2;
  for (int i = 0; i < n; ++i)
    b2.push_back(b[a1[i].second]);

  if (b1 != b2) {
    cout << -1 << endl;
    return;
  }

  b = b1;
  for (int i = 0; i < n; ++i)
    a[i] = a1[i].first;
  **/
  back(a, b);
  cout << ans << endl;
}

int main() {
#ifdef HOME
  ifstream cin("input.in");
  ofstream cout("output.out");
#endif
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);


  /**
  int t1 = 1;
  cout << t1 << endl;
  for (int i = 1; i <= t1; ++i) {
    int n = 1e6;
    cout << n << endl;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; ++i)
      a[i] = 1e9 + i; 

    sort(a.begin(), a.end());
    for (int i = 1; i <= n; ++i)
      b[i] = 1;
    for (int i = 1; i <= n; ++i)
      cout << a[i] << " ";
    cout << endl;
    for (int i = 1; i <= n; ++i)
      cout << b[i] << " ";
    cout << endl;
  }

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

  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

input:

5
1 2 3 4 5
6 6 6 6 7

output:

9

result:

ok 1 number(s): "9"

Test #2:

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

input:

3
2 3 4
1 2 3

output:

-1

result:

ok 1 number(s): "-1"

Test #3:

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

input:

2
65536 65537
1 2

output:

32

result:

ok 1 number(s): "32"

Test #4:

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

input:

1
0
28

output:

28

result:

ok 1 number(s): "28"

Test #5:

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

input:

1
249912
43

output:

26

result:

ok 1 number(s): "26"

Test #6:

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

input:

2
52522336 155670
52532336 165670

output:

10000

result:

ok 1 number(s): "10000"

Test #7:

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

input:

2
141839218 538313890
17731054 67290388

output:

1155

result:

ok 1 number(s): "1155"

Test #8:

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

input:

2
678834913 571995689
84855772 71500869

output:

-1

result:

wrong answer 1st numbers differ - expected: '1411', found: '-1'