QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#46030#2174. Which Planet is This?!dmga44#WA 189ms29432kbC++4.8kb2022-08-24 21:41:442022-08-24 21:41:45

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-24 21:41:45]
  • 评测
  • 测评结果:WA
  • 用时:189ms
  • 内存:29432kb
  • [2022-08-24 21:41:44]
  • 提交

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);

   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(!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: 3ms
memory: 3680kb

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: 189ms
memory: 29432kb

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: 167ms
memory: 25196kb

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'