oj.uz

Submission #658247

# Submission time Handle Problem Language Result Execution time Memory
658247 2022-11-12T14:12:57 Z 600Mihnea Necklace (Subtask 1-3) (BOI19_necklace1) C++17
53 / 85
 1496 ms 992 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-14;

vector<cd> lol, cs, a;

void place(string s, int len, vector<ld>& sol) {
  int n = (int)s.size();
  if (len > n) {
    return;
  }
  ld ang = 2 * PI / len;
  cd c(cos(ang), sin(ang));
  cs.resize(len);
  a.resize(n);
 	sol.clear();
 	sol.resize(n - len + 1, 0);
  cs[0] = 1;
  for (int i = 1; i < len; i++) {
    cs[i] = cs[i - 1] * c;
  }
  for (int i = 0; i < n; i++) {
    a[i] = values[s[i] - 'a'];
  } 
  vector<cd> vl(n, 0);
 	for (int i = 0; i + len - 1 < n; i++) {
 		if (i >= 1) {
 			vl[i] = vl[i - 1];
 			vl[i] -= a[i - 1];
 			vl[i] /= c;
 			vl[i] += cs[len - 1] * a[i + len - 1];
 		} else {
	 		for (int j = 0; j < len; j++) {
	 			vl[i] += cs[j] * a[i + j];
			}
		}
 	}
 	for (int i = 0; i + len - 1 < n; i++) {
 		sol[i] = norm(vl[i]);
 	}
}

string s, t;
vector<ld> norms_s, norms_t;

bool isok(int len) {
  place(s, len, norms_s);
  place(t, len, norms_t);
  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) {
  place(s, len, norms_s);
  place(t, len, norms_t);
  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());
  }
  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)) {
    if (verbose) {
      cout << "len = " << len << "\n";
    }
    len--;
  }
  cout << len << "\n";
  print(len);
  return 0;
}

Compilation message

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

Subtask #1
25.0 / 25.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 10 ms 400 KB Output is correct
9 Correct 14 ms 340 KB Output is correct
10 Correct 20 ms 440 KB Output is correct
11 Correct 21 ms 452 KB Output is correct
12 Correct 13 ms 340 KB Output is correct

Subtask #3
8.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 2 ms 340 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 2 ms 340 KB Output is correct
8 Correct 10 ms 400 KB Output is correct
9 Correct 14 ms 340 KB Output is correct
10 Correct 20 ms 440 KB Output is correct
11 Correct 21 ms 452 KB Output is correct
12 Correct 13 ms 340 KB Output is correct
13 Partially correct 120 ms 808 KB Output is partially correct
14 Correct 103 ms 688 KB Output is correct
15 Partially correct 879 ms 916 KB Output is partially correct
16 Correct 1046 ms 920 KB Output is correct
17 Partially correct 1174 ms 884 KB Output is partially correct
18 Correct 1496 ms 992 KB Output is correct
19 Partially correct 495 ms 752 KB Output is partially correct
20 Correct 759 ms 808 KB Output is correct
21 Correct 810 ms 808 KB Output is correct