제출 #1356003

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1356003		Aviansh	Portal (BOI24_portal)	C++20	40 / 100	2094 ms	2204 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define int long long

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    array<int,2>pts[n];
    for(int i = 0;i<n;i++){
        cin >> pts[i][0];
        cin >> pts[i][1];
    }
    random_shuffle(pts,pts+n);
    for(int i = n-1;i>=0;i--){
        pts[i][0]-=pts[0][0];
        pts[i][1]-=pts[0][1];
    }
    int curx=0;
    int cury=0;
    int gx = 0;
    int gy = 0;
    set<int>pos;
    pos.insert(0);
    ///origin shifted.
    for(int i = 1;i<n;i++){
        if(pts[i][0]!=0){
            gx=gcd(gx,pts[i][0]);
        }
        if(pts[i][1]!=0){
            gy=gcd(gy,pts[i][1]);
        }
        set<int>rem;
        for(int z : pos){
            if(gcd(gcd(pts[i][0],pts[i][1]),curx)==curx&&gcd(gcd(pts[i][0],pts[i][1]),cury)==cury){
                break;
            }
            int tx = pts[z][0];
            int ty = pts[z][1];
            if(gcd(gcd(tx,ty),curx)==curx&&gcd(gcd(tx,ty),cury)==cury){
                rem.insert(z);
                continue;
            }
            ///for finding dx
            int gc = gcd(abs(pts[i][1]),abs(ty));
            if(gc){
                int a = -((ty)/gc);
                int b = (pts[i][1])/gc;

                int dx = a*pts[i][0]+b*tx;
                dx=abs(dx);
                if(curx==0){
                    curx=dx;
                }
                else if(dx!=0){
                    curx=gcd(curx,dx);
                }
            }
            ///for finding dy
            gc = gcd(abs(pts[i][0]),abs(tx));
            if(gc){
                int a = -((tx)/gc);
                int b = (pts[i][0])/gc;

                int dy = a*pts[i][1]+b*ty;
                dy=abs(dy);
                if(cury==0){
                    cury=dy;
                }
                else if(dy!=0){
                    cury=gcd(cury,dy);
                }
            }
        }
        for(int j : rem){
            pos.erase(j);
        }
        pos.insert(i);
        if(gcd(gcd(pts[i][0],pts[i][1]),curx)==curx&&gcd(gcd(pts[i][0],pts[i][1]),cury)==cury){
            pos.erase(i);
        }
    }
    if(curx==0||cury==0){
        cout << -1;
    }
    else{
        if(gx==0||gy==0){
            cout << -1;
        }
        else{
            cout << max(curx*gy,cury*gx);
        }
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'int main()':
Main.cpp:17:19: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = array<long long int, 2>*]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
   17 |     random_shuffle(pts,pts+n);
      |     ~~~~~~~~~~~~~~^~~~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from Main.cpp:1:
/usr/include/c++/13/bits/stl_algo.h:4581:5: note: declared here
 4581 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~

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