QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#441031 | #2174. Which Planet is This?! | ZSH_ZSH | WA | 437ms | 28392kb | C++14 | 3.0kb | 2024-06-14 10:26:52 | 2024-06-14 10:26:52 |
Judging History
answer
#include<bits/stdc++.h>
#define rep(i,a,b) for (int i=(a);i<=(b);i++)
#define drep(i,a,b) for (int i=(a);i>=(b);i--)
typedef long long ll;
using namespace std;
#define debug if (n==400000)
#define fir first
#define sec second
typedef vector<int> vi;
const int D=10000;
const int W=180*D;
int norm(int x)
{
if (x<-W) x+=W;
if (x>W) x-=W;
assert(-W<=x&&x<=W);
return x;
}
vi work(vi a,vi b) // t-s
{
assert(a.size()==b.size());
int n=a.size();
vector<int> s,t;
rep(i,0,n-2)
{
s.push_back(a[i+1]-a[i]);
t.push_back(b[i+1]-b[i]);
}
s.push_back(a[0]-a.back()+2*W);
t.push_back(b[0]-b.back()+2*W);
// printf("a : "); for (auto x:a) printf("%.3lf ",x); printf("\n");
// printf("b : "); for (auto x:b) printf("%.3lf ",x); printf("\n");
// printf("s : "); for (auto x:s) printf("%.3lf ",x); printf("\n");
// printf("t : "); for (auto x:t) printf("%.3lf ",x); printf("\n");
vi fail(n);
fail[0]=-1;
for (int i=1,j=-1;i<n;i++)
{
while (j!=-1&&t[j+1]!=t[i]) j=fail[j];
if (t[j+1]==t[i]) j++;
fail[i]=j;
}
vi ang;
rep(i,0,n-1) s.push_back(s[i]);
int mat=-1;
rep(i,0,2*n-1)
{
assert(mat!=n-1);
while (mat!=-1&&s[i]!=t[mat+1]) mat=fail[mat];
if (s[i]==t[mat+1])
{
mat++;
if (mat==n-1)
{
int x=norm(a[(i+1)%n]-b[0]);
ang.push_back(x);
ang.push_back(x+2*W);
ang.push_back(x-2*W);
mat=fail[mat];
}
}
}
return ang;
}
vi merge(vi x,vi y)
{
vector<pair<int,int> > v;
for (auto it:x) v.push_back({it,0});
for (auto it:y) v.push_back({it,1});
sort(v.begin(),v.end());
vi z;
for (int i=0;i<v.size();i++)
{
int j=i;
while (j+1<v.size()&&v[i].fir==v[j+1].fir) j++;
bool ok[2]={0,0};
rep(k,i,j) ok[v[k].sec]=1;
if (ok[0]&&ok[1]) z.push_back(v[i].fir);
i=j;
}
return z;
}
int fuck(double x)
{
x+=0.1;
return x;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0);
int n; cin>>n;
vector<pair<pair<int,int>,int> > v;
rep(i,0,n-1)
{
double x,y; cin>>x>>y;
x+=90; y+=180;
x*=D,y*=D;
v.push_back({{fuck(x),fuck(y)},0});
}
rep(i,0,n-1)
{
double x,y; cin>>x>>y;
x+=90; y+=180;
x*=D,y*=D;
v.push_back({{fuck(x),fuck(y)},1});
}
sort(v.begin(),v.end());
vector<vi> A;
for (int i=0;i<v.size();i++)
{
int j=i;
while (j+1<v.size()&&v[i].fir.fir==v[j+1].fir.fir) j++;
vi w[2];
assert(!w[0].size());
assert(!w[1].size());
rep(k,i,j) w[v[k].sec].push_back(v[k].fir.sec);
rep(k,0,1) sort(w[k].begin(),w[k].end());
if (w[0].size()!=w[1].size())
{
printf("Different\n");
debug printf("ahahah\n");
return 0;
}
auto t=work(w[0],w[1]);
if (!t.size())
{
printf("Different\n");
debug printf("here\n");
return 0;
}
A.push_back(t);
i=j;
}
rep(i,1,(int)A.size()-1) A[0]=merge(A[0],A[i]);
if (A[0].size()) printf("Same\n");
else printf("Different\n");
debug printf("end here\n");
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 4116kb
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: 316ms
memory: 28356kb
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: 0
Accepted
time: 259ms
memory: 25728kb
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:
Same
result:
ok single line: 'Same'
Test #4:
score: -100
Wrong Answer
time: 437ms
memory: 28392kb
input:
400000 -57.6217 51.8207 -66.4301 79.8153 68.6538 169.5723 -48.0781 -6.6298 -6.7822 -17.1276 -39.4009 179.3474 63.3867 -77.7996 61.0296 23.9060 -45.3758 41.1641 70.4582 129.4273 -29.7325 -35.5175 -15.3621 31.2737 -23.1798 102.5020 80.7571 -132.1432 -48.3888 -6.5756 18.4703 135.7623 -0.8199 -65.5536 -...
output:
Different end here
result:
wrong answer 1st lines differ - expected: 'Same', found: 'Different'