# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
997515 |
2024-06-12T12:52:51 Z |
hengliao |
Portal (BOI24_portal) |
C++17 |
|
40 ms |
6708 KB |
#include<bits/stdc++.h>
#include <chrono>
#include <random>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;
struct P{
ll x, y;
bool operator< (const P &tar) const{
if(x!=tar.x){
return x<tar.x;
}
return y<tar.y;
}
};
void solve(){
ll n;
cin>>n;
vector<P> p(n);
for(auto &it:p){
cin>>it.x>>it.y;
}
if(n==1){
cout<<"-1\n";
return;
}
set<ll> st;
for(auto &it:p){
st.insert(it.x);
}
if(st.size()<=1){
cout<<"-1\n";
return;
}
ll gcd1=(*prev(st.end()))-(*st.begin());
ll pre=(*st.begin());
for(auto &it:st){
if(it==*st.begin()) continue;
gcd1=__gcd(gcd1, it-pre);
pre=it;
}
st.clear();
for(auto &it:p){
st.insert(it.y);
}
if(st.size()<=1){
cout<<"-1\n";
return;
}
ll gcd2=(*prev(st.end()))-(*st.begin());
pre=(*st.begin());
for(auto &it:st){
if(it==*st.begin()) continue;
gcd2=__gcd(gcd2, it-pre);
pre=it;
}
bool type1=1;
pll comp={(p[1].x-p[0].x)/gcd1, (p[1].y-p[0].y)/gcd2};
for(ll i=2;i<n;i++){
ll f=(p[i].x-p[0].x)/gcd1;
ll s=(p[i].y-p[0].y)/gcd2;
if(comp.F!=f || comp.S!=s){
type1=0;
break;
}
}
if(type1){
cout<<"-1\n";
return;
}
bool type2=1;
for(ll i=1;i<n;i++){
ll f=(p[i].x-p[0].x)/gcd1;
ll s=(p[i].y-p[0].y)/gcd2;
if((abs(f+s))%2!=0){
type2=0;
break;
}
}
if(type2){
cout<<gcd1*gcd2*2<<'\n';
return;
}
cout<<gcd1*gcd2<<'\n';
return;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
solve();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
600 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
600 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
21 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
19 ms |
1880 KB |
Output is correct |
3 |
Correct |
20 ms |
1884 KB |
Output is correct |
4 |
Correct |
19 ms |
2040 KB |
Output is correct |
5 |
Correct |
30 ms |
1884 KB |
Output is correct |
6 |
Correct |
18 ms |
1884 KB |
Output is correct |
7 |
Correct |
38 ms |
6708 KB |
Output is correct |
8 |
Correct |
38 ms |
6472 KB |
Output is correct |
9 |
Correct |
40 ms |
6484 KB |
Output is correct |
10 |
Correct |
32 ms |
4336 KB |
Output is correct |
11 |
Correct |
32 ms |
4336 KB |
Output is correct |
12 |
Correct |
28 ms |
4184 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
21 ms |
2028 KB |
Output is correct |
15 |
Correct |
19 ms |
1884 KB |
Output is correct |
16 |
Correct |
26 ms |
2024 KB |
Output is correct |
17 |
Correct |
21 ms |
1884 KB |
Output is correct |
18 |
Correct |
27 ms |
2024 KB |
Output is correct |
19 |
Correct |
21 ms |
1884 KB |
Output is correct |
20 |
Correct |
26 ms |
1884 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
6 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
600 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
21 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
600 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
0 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
348 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
348 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
21 |
Halted |
0 ms |
0 KB |
- |