QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#60651 | #2174. Which Planet is This?! | captured# | WA | 401ms | 23992kb | C++17 | 4.1kb | 2022-11-05 22:15:36 | 2022-11-05 22:15:50 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
#define LL long long
#define FOR(i,n) for(int i=0;i<n;i++)
#define deb(x) cerr<<#x<<" : "<<x<<" "
#define dnl cerr<<endl
const LL base[2] = {37,59};
const LL mod[2] = {(LL)1e9+7,(LL)1e9+9};
const int maxn = 4e6+40;
LL P[2][maxn];
LL H[2][maxn];
LL R[2][maxn];
LL inv[2][maxn];
inline LL power(LL a,LL b,const int m){
if(b==0)return 1;
if(b==1)return a%m;
LL x = power(a,b/2,m);
x = (x*x)%m;
if(b%2 != 0){
x = (x*a)%m;
}
return x;
}
inline LL range_hash(int idx,int l,int r){
LL h = H[idx][r]-H[idx][l-1]+mod[idx];
h %= mod[idx];
if(l>0)h *= inv[idx][l-1];
h %= mod[idx];
// cerr<<"Shoja :";
// deb(idx);deb(l);deb(r);deb(h);dnl;
return h;
}
int n;
inline LL reverse_hash(int idx,int l,int r){
LL h = R[idx][l] - R[idx][r+1] + mod[idx];
h %= mod[idx];
int bad = n-r;
if(bad>0){
h *= inv[idx][bad];
h %= mod[idx];
}
// cerr<<"Ulta :";
// deb(idx);deb(l);deb(r);deb(h);dnl;
return h;
}
inline LL drevhash(int l,int r){
LL x = reverse_hash(0,l,r);
LL y = reverse_hash(1,l,r);
return (x<<31)^y;
}
inline LL dhash(int l,int r){
LL x = range_hash(0,l,r);
LL y = range_hash(1,l,r);
return (x<<31)^y;
}
int finpref(int l,int n){
int lo=1,hi=(n-l)+1;
hi /= 2;
int ans = 0;
for(int mid=lo;mid<=hi;mid++){
if( dhash(l,l+mid-1)==drevhash(l+mid,l+mid+mid-1) ){
ans = mid;
return ans;
}
}
// while(lo<=hi){
// int mid = (lo+hi)>>1;
// deb(l);deb(n);deb(mid);dnl;
// if( dhash(l,l+mid-1)==drevhash(l+mid,l+mid+mid-1) ){
// ans = mid;
// lo = mid+1;
// }
// else hi = mid-1;
// }
return ans;
}
int finsuff(int l,int n){
int lo=1,hi=(n-l)+1;
hi /= 2;
int ans = 0;
for(int mid=lo;mid<=hi;mid++){
if( dhash(n-mid+1,n)==drevhash(n-mid-mid+1,n-mid) ){
ans = mid;
return ans;
}
}
// while(lo<=hi){
// int mid = (lo+hi)>>1;
//// deb(mid);dnl;
// if( dhash(n-mid+1,n)==drevhash(n-mid-mid+1,n-mid) ){
// ans = mid;
// lo = mid+1;
// }
// else hi = mid-1;
// }
return ans;
}
//#define cnd tree[idx]
//#define lnd idx*2,b,(b+e)/2
//#define rnd idx*2+1,(b+2)/2 + 1,e
//#define lc tree[idx*2]
//#define lr tree[idx*2+1]
//typedef pair<int,int> pii;
//struct segtree{
// pii tree[4*maxn] ;
// void build(int idx,int b,int e,int val){
// cnd=pii(val,-1);
// if(b!=e){
// build(lnd);
// build(rnd);
// }
// }
// void update(int idx,int b,int e)
//};
void solve(int cs){
double n, sum = 0, sum2 = 0;
vector<double> a,b;
cin>>n;
for (int i = 0; i < n; i++) {
double x, y;
cin>>x>>y;
sum+=y;
a.push_back(x);
b.push_back(y);
}
vector<double> a2,b2;
for (int i = 0; i < n; i++) {
double x, y;
cin>>x>>y;
sum2+=y;
a2.push_back(x);
b2.push_back(y);
}
sort(a.begin(), a.end());
sort(a2.begin(), a2.end());
for (int i = 0; i < n; i++) {
if (fabs(a[i] - a2[i]) > 1e-9) {
cout<<"Different"<<endl;
return;
}
}
sum = sum2 - sum; sum /= n;
sort(b.begin(), b.end());
for (int i = 0; i<n; i++) {
b2[i] = b2[i] - sum;
while (b2[i] > 180) {
b2[i] -= 180;
}
while (b2[i] <= -180) {
b2[i] += (180);
}
}
sort(b2.begin(), b2.end());
for (int i = 0; i < n; i++) {
if (fabs(b[i] - b2[i]) > 1e-9) {
cout<<"Different"<<endl;
return;
}
//cout<<b[i]<<" "<<b2[i]<<endl;
}
cout<<"Same"<<endl;
}
/*
ATTAATTA
*/
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int t=1;
// cin>>t;
for(int cs=1;cs<=t;cs++)solve(cs);
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3536kb
input:
3 10 0 20 40 30 -15 40 -15 20 0 30 40
output:
Different
result:
ok single line: 'Different'
Test #2:
score: -100
Wrong Answer
time: 401ms
memory: 23992kb
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:
Different
result:
wrong answer 1st lines differ - expected: 'Same', found: 'Different'