QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#441034#2174. Which Planet is This?!ZSH_ZSHWA 543ms30720kbC++143.1kb2024-06-14 10:29:152024-06-14 10:29:15

Judging History

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

  • [2024-06-14 10:29:15]
  • 评测
  • 测评结果:WA
  • 用时:543ms
  • 内存:30720kb
  • [2024-06-14 10:29:15]
  • 提交

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;
	map<int,int> mp;
	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;
		debug
		{
			printf("ang %d : ",v[i].fir.fir);
			for (auto x:t) printf("%d ",x);
			printf("\n");
		}
	}
	
	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: 3892kb

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: 310ms
memory: 30720kb

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: 248ms
memory: 24852kb

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: 543ms
memory: 27964kb

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:

ang 14 : -976990 2623010 -4576990 -976990 2623010 -4576990 
ang 16 : 823010 4423010 -2776990 
ang 31 : -976990 2623010 -4576990 -976990 2623010 -4576990 
ang 36 : -976990 2623010 -4576990 -976990 2623010 -4576990 
ang 37 : 823010 4423010 -2776990 823010 4423010 -2776990 
ang 42 : 823010 4423010 -277...

result:

wrong answer 1st lines differ - expected: 'Same', found: 'ang 14 : -976990 2623010 -4576990 -976990 2623010 -4576990 '