QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#46033 | #2174. Which Planet is This?! | dmga44# | WA | 190ms | 28508kb | C++ | 4.9kb | 2022-08-24 21:58:50 | 2022-08-24 21:58:53 |
Judging History
answer
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast","unroll-loops","omit-frame-pointer","inline")
#pragma GCC optimization("O3")
using namespace std;
///Macros
#define int long long
#define it(x) x::iterator
#define pb push_back
#define pf push_front
#define lb lower_bound
#define up upper_bound
#define fs first
#define sc second
#define endl '\n'
#define pf push_front
#define all(x) x.begin() , x.end()
#define sz(x) (int)(x.size())
#define FOR(i,a,n) for(int i=a;i<(n);i++)
#define FO(i,n) for(int i=0;i<(n);i++)
#define RFOR(i,a,n) for(int i=(n)-1;i>=a;i--)
#define RFO(i,n) for(int i=(n)-1;i>=0;i--)
#define gof(i,n) for(auto &i: n);
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector< ii > vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
///Constraints:
const int inf = ((1ll<<31ll)-1ll);
const int INF = (((1ll<<59ll)-1ll)*2ll)+1ll;
const ull mod = 998244353;
const ld pi = acos(-1);
/// Functions:
#define lg2(x) 31 - __builtin_clz(x)
#define lg2ll(x) 63 - __builtin_clzll(x)
#define lgx(x,b) ( log(x) / log(b) )
#define YN(x) cout<<((x)?("YES"):("NO"))<<fl;
#define yn(x) cout<<((x)?("Yes"):("No"))<<fl;
/*void print(vector<int>v){for(auto that:v)cout<<that<<" ";cout<<endl;}
vector<int>read(int cnt){vi v(cnt);for(int i=0;i<cnt;i++)cin>>v[i];return v;}*/
/*#include<ext/pb_ds/assoc_container.hpp> // Common file
#include<ext/pb_ds/tree_policy.hpp> // Including tree_order_statistics_node_update
using namespace __gnu_pbds;
//comenta el define long long int
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;*/
// find_by_order
// order_of_key
/// Quick Pow------------------------------------------------
int qpow(int b,int e)
{
if( !e ) return 1;
if( e & 1 ) return qpow(b,e-1) * b %mod ;
int pwur = qpow(b,e>>1);
return pwur * pwur %mod;
}
///Inverso Modular
int InverM(int a,int b)
{
int eso=a-(a/b)*b;
if(eso==0)
return 0;
int ans=(1-b*InverM(b,eso))/eso;
if(ans<0)
ans+=b;
return ans;
}
const int MAXN=3600000;
int read(string s){
int a=0;
int cont=0;
bool b=false;
bool c=false;
for(int i=0;i<sz(s);i++){
if(s[i]=='-'){
c=true;
continue;
}
if(s[i]=='.'){
b=true;
continue;
}
a*=10;
a+=s[i]-'0';
if(b)
cont++;
}
a*=qpow(10,4-cont);
if(c)
a*=-1;
return a;
}
/// Variables------------------------------------------------
int tc,n,m,k,q;
bool F;
void Fun(vector<int>&A, vector<int>&B){
if(F){
return;
}
int a=-1;
int c=inf;
int b=-1;
int curB=-1;
sort(all(A));
sort(all(B));
for(int i=0;i<sz(A);i++){
int best=A[i]-A[(i+1)%sz(A)];
best+=MAXN;
best%=MAXN;
if(best>curB){
a=i;
curB=best;
}
c=min(best,c);
}
curB=-1;
for(int i=0;i<sz(A);i++){
int best=A[i]-A[(i+1)%sz(A)];
best+=MAXN;
best%=MAXN;
if(best>curB){
b=i;
curB=best;
}
}
if(c==(A[a]-A[(a+1)%sz(A)]+MAXN)%MAXN){
int dist=(B[b]-A[a]-k+MAXN)%MAXN;
if(c==0)
c=MAXN;
int d=__gcd(c,m);
if(dist%d!=0){
F=true;
k=0;
}
int h1=c/d;
int h2=m/d;
int h3=dist/d;
int ans=h3*(InverM(h2,h1));
ans%=h1;
int X=ans*m;
k+=X;
k%=MAXN;
if(m==1){
m=c;
}else{
m=(m*c)/(__gcd(m,c));
}
}else{
F=true;
k=(B[b]-A[a]+MAXN)%MAXN;
}
}
void problem()
{
cin>>n;
vector<ii> A;
vector<ii> B;
m=-1;
F=false;
k=0;
for(int i=0;i<n;i++){
string s;
cin>>s;
int a=read(s);
string s1;
cin>>s1;
int b=read(s1);
b+=MAXN;
b%=MAXN;
A.pb({a,b});
}
for(int i=0;i<n;i++){
string s;
cin>>s;
int a=read(s);
cin>>s;
int b=read(s);
b+=MAXN;
b%=MAXN;
B.pb({a,b});
}
sort(all(A));
sort(all(B));
vector<int> Cur1;
vector<int> Cur2;
Cur1.pb(A[0].sc);
Cur2.pb(B[0].sc);
if(A[0].fs!=B[0].fs){
cout<<"Different";
return;
}
for(int i=1;i<n;i++){
if(A[i].fs!=B[i].fs){
cout<<"Different";
return;
}
if(A[i].fs!=A[i-1].fs){
Fun(Cur1,Cur2);
Cur1.resize(0);
Cur2.resize(0);
}
Cur1.pb(A[i].sc);
Cur2.pb(B[i].sc);
}
Fun(Cur1,Cur2);
if(MAXN%m){
cout<<"Different";
}
if(!F){
cout<<"Same";
return;
}
for(int i=0;i<n;i++){
A[i].sc+=k;
A[i].sc%=MAXN;
}
sort(all(A));
for(int i=0;i<n;i++){
if(A[i]!=B[i]){
cout<<"Different";
return;
}
}
cout<<"Same";
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.setf(ios::fixed);
cout.precision(0);
//freopen("a.in","w",stdin)
//freopen("a.out","w",stdout);
// cin>>tc;
tc=1;
while(tc--)
{
problem();
cout<<endl;
}
}
///Tips
//Busqueda Binaria
//Precomputing
//Dinamic Programming
//Revisar constraints
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3672kb
input:
3 10 0 20 40 30 -15 40 -15 20 0 30 40
output:
Different
result:
ok single line: 'Different'
Test #2:
score: 0
Accepted
time: 190ms
memory: 28508kb
input:
359998 -0.0045 96.8638 -0.0045 -79.2284 -0.0045 -50.4113 -0.0045 -79.0394 -0.0045 -24.9710 -0.0045 -142.9880 -0.0045 50.6344 -0.0045 125.9464 -0.0045 -17.3039 -0.0045 42.3454 -0.0045 130.6138 -0.0045 -106.4363 -0.0045 -95.9378 -0.0045 90.7312 -0.0045 75.7615 -0.0045 -66.9785 -0.0045 -81.0752 -0.0045...
output:
Same
result:
ok single line: 'Same'
Test #3:
score: -100
Wrong Answer
time: 159ms
memory: 26240kb
input:
299998 -0.0045 -42.0335 -0.0045 -106.8631 -0.0045 176.8211 -0.0045 100.6703 -0.0045 168.0453 -0.0045 -100.7977 -0.0045 -31.7881 -0.0045 -43.3799 -0.0045 -87.3392 -0.0045 30.4474 -0.0045 -7.4550 -0.0045 106.5476 -0.0045 -3.9185 -0.0045 -56.8153 -0.0045 -146.7755 -0.0045 -76.6043 -0.0045 57.1774 -0.00...
output:
Different
result:
wrong answer 1st lines differ - expected: 'Same', found: 'Different'