oj.uz

답안 #656112

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
656112 2022-11-06T10:03:31 Z 600Mihnea Necklace (Subtask 1-3) (BOI19_necklace1) C++17
45 / 85
 1500 ms 504 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];

cd get(string s, cd c) {
  cd sol = 0;
  cd cur = 1;
  for (int i = 0; i < (int) s.size(); i++) {
    sol += cur * values[s[i] - 'a'];
    cur *= c;
  }
  return sol;
}

const ld eps = 1e-6;

bool same(string s, string t) {
  assert((int) s.size() == (int) t.size());
  int n = (int) s.size();
  ld ang = 2 * PI / n;
  cd c(cos(ang), sin(ang));
  return abs(norm(get(s, c)) - norm(get(t, c))) < eps;
}

string s, t;

bool isok(int len) {
  ld ang = 2 * PI / len;
  cd c(cos(ang), sin(ang));
  int n = (int) s.size();
  int m = (int) t.size();
  if (len > n || len > m) {
    return 0;
  }
  vector<ld> norms_s(n - len + 1);
  vector<ld> norms_t(m - len + 1);
  for (int i = 0; i < n - len + 1; i++) {
    norms_s[i] = norm(get(string(s.begin() + i, s.begin() + i + len), c));
  }
  for (int i = 0; i < m - len + 1; i++) {
    norms_t[i] = norm(get(string(t.begin() + i, t.begin() + i + len), c));
  }
  n = (int) norms_s.size();
  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) {
  ld ang = 2 * PI / len;
  cd c(cos(ang), sin(ang));
  int n = (int) s.size();
  int m = (int) t.size();
  vector<ld> norms_s(n - len + 1);
  vector<ld> norms_t(m - len + 1);
  for (int i = 0; i < n - len + 1; i++) {
    norms_s[i] = norm(get(string(s.begin() + i, s.begin() + i + len), c));
  }
  for (int i = 0; i < m - len + 1; i++) {
    norms_t[i] = norm(get(string(t.begin() + i, t.begin() + i + len), c));
  }
  n = (int) norms_s.size();
  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:112:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |     freopen ("___input___.txt", "r", stdin);
      |     ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 3 ms 340 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 3 ms 340 KB Output is correct
6 Correct 7 ms 340 KB Output is correct
7 Correct 10 ms 364 KB Output is correct
8 Correct 79 ms 340 KB Output is correct
9 Correct 98 ms 344 KB Output is correct
10 Correct 117 ms 376 KB Output is correct
11 Correct 126 ms 376 KB Output is correct
12 Correct 95 ms 380 KB Output is correct

Subtask #3
0.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 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 3 ms 340 KB Output is correct
6 Correct 7 ms 340 KB Output is correct
7 Correct 10 ms 364 KB Output is correct
8 Correct 79 ms 340 KB Output is correct
9 Correct 98 ms 344 KB Output is correct
10 Correct 117 ms 376 KB Output is correct
11 Correct 126 ms 376 KB Output is correct
12 Correct 95 ms 380 KB Output is correct
13 Execution timed out 1577 ms 504 KB Time limit exceeded
14 Halted 0 ms 0 KB -