QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#441029 | #2174. Which Planet is This?! | ZSH_ZSH | WA | 307ms | 28460kb | C++14 | 2.8kb | 2024-06-14 10:24:38 | 2024-06-14 10:24:39 |
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 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*=D,y*=D;
v.push_back({{fuck(x),fuck(y)},0});
}
rep(i,0,n-1)
{
double x,y; cin>>x>>y;
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");
return 0;
}
auto t=work(w[0],w[1]);
if (!t.size())
{
printf("Different\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");
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 4124kb
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: 307ms
memory: 28460kb
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'