oj.uz

Submission #658248

# Submission time Handle Problem Language Result Execution time Memory
658248 2022-11-12T14:15:26 Z 600Mihnea Necklace (Subtask 1-3) (BOI19_necklace1) C++17
85 / 85
 1443 ms 1048 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-10;

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 340 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 340 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 340 KB Output is correct
9 Correct 13 ms 340 KB Output is correct
10 Correct 18 ms 444 KB Output is correct
11 Correct 21 ms 340 KB Output is correct
12 Correct 14 ms 340 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 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 340 KB Output is correct
9 Correct 13 ms 340 KB Output is correct
10 Correct 18 ms 444 KB Output is correct
11 Correct 21 ms 340 KB Output is correct
12 Correct 14 ms 340 KB Output is correct
13 Correct 114 ms 696 KB Output is correct
14 Correct 112 ms 824 KB Output is correct
15 Correct 891 ms 1000 KB Output is correct
16 Correct 1026 ms 888 KB Output is correct
17 Correct 1058 ms 880 KB Output is correct
18 Correct 1443 ms 1048 KB Output is correct
19 Correct 466 ms 752 KB Output is correct
20 Correct 777 ms 860 KB Output is correct
21 Correct 873 ms 808 KB Output is correct