Submission #994723

#	Time	Username	Problem	Language	Result	Execution time	Memory
994723		PenguinsAreCute	Portal (BOI24_portal)	C++17	50 / 100	80 ms	4304 KiB

Main

// yay linear algebra!
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int SQDET = 1414218;
bool pr[SQDET];
vector<int> primes;
int test(int x[], int y[], int n, int p) {
	// test against the guy with gcd with lowest vp.
	pair<int,int> l = {100,0};
	for(int i=1;i<n;i++) {
		int g = __gcd(x[i],y[i]), c = 0;
		while((!(g%p)) && c<100) g/=p, c++;
		l=min(l,{c,i});
	}
	int g = 0;
	for(int i=1;i<n;i++) g=__gcd(g,x[i]*y[l.second]-x[l.second]*y[i]);
	int c = 0; while(!(g%p)) g/=p,c++;
	return c;
}
main() {
	fill(pr,pr+SQDET,1);
	for(int i=2;i<SQDET;i++) if(pr[i]) {
		primes.push_back(i);
		for(int j=i*i;j<SQDET;j+=i) pr[j]=0;
	}
	int n; cin >> n;
	int x[n], y[n]; for(int i=0;i<n;i++) cin>>x[i]>>y[i];
	for(int i=1;i<n;i++) x[i]-=x[0],y[i]-=y[0];
	int g=0; for(int i=2;i<n;i++) g=__gcd(g,x[1]*y[i]-x[i]*y[1]);
	if(!g) {cout<<-1; return 0;}
	int ans = 1;
	for(auto i: primes) if(!(g%i)) {
		int k = test(x,y,n,i);
		while(k--) ans *= i;
		while(!(g%i)) g/=i;
	}
	if(g>1 && test(x,y,n,g)) ans *= g;
	cout << ans;
}

Compilation message (stderr)

Main.cpp:21:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   21 | main() {
      | ^~~~

• Subtask 1: 1 / 1
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 29 / 29
• Subtask 5: 0 / 15
• Subtask 6: 0 / 35