oj.uz

Submission #656119

# Submission time Handle Problem Language Result Execution time Memory
656119 2022-11-06T10:13:51 Z 600Mihnea Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 1500 ms 540 KB 
bool home = 0;
bool verbose = 1;

#include <bits/stdc++.h>

using namespace std;

mt19937 rng(7777);

typedef long double ld;

const ld PI = 3.14159265358979323846264338327950288419716939937510582097494459230781640628620899862803482534211706798214808651328230664709384460955058223172535940812848111745028410270193852110555964462294895493038196442881097566593344612847564823378678316527120190914;
using cd = complex<ld>;

ld values[26];

const ld eps = 1e-6;

vector<ld> place(string s, int len) {
  int n = (int) s.size();
  if (len > n) {
    return {};
  }
  ld ang = 2 * PI / len;
  cd c(cos(ang), sin(ang));
  vector<cd> cs(len);
  cs[0] = 1;
  for (int i = 1; i < len; i++) {
    cs[i] = cs[i - 1] * c;
  }

  vector<ld> a(n);
  for (int i = 0; i < n; i++) {
    a[i] = values[s[i] - 'a'];
  }
  vector<cd> ret(n - len + 1);
  vector<ld> sol(n - len + 1);
  for (int i = 0; i < n - len + 1; i++) {
    for (int j = 0; j < len; j++) {
      ret[i] += cs[j] * a[i + j];
    }
  }
  for (int i = 0; i < n - len + 1; i++) {
    sol[i] = norm(ret[i]);
  }
  return sol;
}

string s, t;


bool isok(int len) {
  vector<ld> norms_s = place(s, len);
  vector<ld> norms_t = place(t, len);
  int n = (int) norms_s.size();
  int m = (int) norms_t.size();
  sort(norms_s.begin(), norms_s.end());
  sort(norms_t.begin(), norms_t.end());
  int j = 0;
  for (int i = 0; i < n; i++) {
    while (j < m && norms_t[j] < norms_s[i]) {
      j++;
    }
    if (0 <= j && j < m && abs(norms_s[i] - norms_t[j]) < eps) {
      return 1;
    }
    if (0 <= j - 1 && j - 1 < m && abs(norms_s[i] - norms_t[j - 1]) < eps) {
      return 1;
    }
  }
  return 0;
}

void print(int len) {
  vector<ld> norms_s = place(s, len);
  vector<ld> norms_t = place(t, len);
  int n = (int) norms_s.size();
  int m = (int) norms_t.size();
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (abs(norms_s[i] - norms_t[j]) < eps) {
        cout << i << " " << j << "\n";
        exit(0);
      }
    }
  }
}

int main() {
  for (int x = 0; x < 26; x++) {
    values[x] = cos(rng()) * 10;
  }
  if (!home) {
    verbose = 0;
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
  }
  if (home) {
    verbose = 1;
    freopen ("___input___.txt", "r", stdin);
  }

  cin >> s >> t;
  int n = (int) s.size(), m = (int) t.size();
  int len = min(n, m);
  while (!isok(len)) {
    len--;
  }
  cout << len << "\n";
  print(len);
  return 0;
}

Compilation message

necklace.cpp: In function 'int main()':
necklace.cpp:101:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |     freopen ("___input___.txt", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 12 ms 340 KB Output is correct
7 Correct 21 ms 420 KB Output is correct
8 Correct 100 ms 380 KB Output is correct
9 Correct 129 ms 384 KB Output is correct
10 Correct 155 ms 424 KB Output is correct
11 Correct 177 ms 412 KB Output is correct
12 Correct 141 ms 424 KB Output is correct

Subtask #3
0.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 4 ms 340 KB Output is correct
6 Correct 12 ms 340 KB Output is correct
7 Correct 21 ms 420 KB Output is correct
8 Correct 100 ms 380 KB Output is correct
9 Correct 129 ms 384 KB Output is correct
10 Correct 155 ms 424 KB Output is correct
11 Correct 177 ms 412 KB Output is correct
12 Correct 141 ms 424 KB Output is correct
13 Execution timed out 1580 ms 540 KB Time limit exceeded
14 Halted 0 ms 0 KB -