結果
問題 | No.1544 [Cherry 2nd Tune C] Synchroscope |
ユーザー |
|
提出日時 | 2021-07-06 20:19:00 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,844 bytes |
コンパイル時間 | 1,605 ms |
コンパイル使用メモリ | 169,036 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-01 12:12:48 |
合計ジャッジ時間 | 5,762 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 32 WA * 16 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define REP(i,n) for (int i = 0; i < (n); ++i) #define DREP(i,s,n) for(int i = (s); i < (n); i++) template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;} template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;} using ll = long long; using P = pair<int,int>; using Pl = pair<long long,long long>; using veci = vector<int>; using vecl = vector<long long>; using vecveci = vector<vector<int>>; using vecvecl = vector<vector<long long>>; const int MOD = 1000000007; const double pi = acos(-1); ll gcd(ll a, ll b) {if(b == 0) return a; else return gcd(b,a%b);} ll lcm(ll a, ll b) {return a*b/gcd(a,b);} void ex_gcd(ll a, ll b, ll &x, ll &y) { if(b == 0) { x = 1, y = 0; return; } ex_gcd(b,a%b,y,x); y -= (a/b)*x; } int main() { int N,M; cin >> N >> M; veci A(N),B(M); REP(i,N) cin >> A[i]; REP(i,M) cin >> B[i]; ll ans = 1LL<<60; for(int i = 0; i < N; i++) { for(int j = 0; j < M; j++) { if(A[i] != B[j]) continue; if(i == j) { ans = min(ans,(ll)i); continue; } int g = gcd(N,gcd(M,abs(j-i))); if(gcd(N,M) != 1) continue; ll x,y; ex_gcd(N/g,M/g,x,y); x *= j-i; y *= j-i; //cout << x << " " << y << endl; ll l = -x/M + (abs(-x)%M != 0 && -x >= 0); l = max(l,0LL); ll r = -y/N - (abs(-y)%N != 0 && -y <= 0); r = min(r,0LL); //cout << l << " " << r << endl; ll m = l; // cout << m << endl; ans = min((ll)ans,i+(m*M+x)*N); } } if(ans != 1LL<<60) cout << ans+1 << endl; else cout << -1 << endl; return 0; }