Submission #1076245

#	Time	Username	Problem	Language	Result	Execution time	Memory
1076245		oscar1f	Portal (BOI24_portal)	C++17	100 / 100	23 ms	3532 KiB

Main

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int TAILLE_MAX=100*1000+5;
int nbPort,ligPrem,colPrem,pgcd;
int mat[2][TAILLE_MAX];
vector<int> listeNonNul;

void afficher() {
    for (int i=0;i<2;i++) {
        for (int j=0;j<nbPort-1;j++) {
            cout<<mat[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;
}

void echange(int colDeb,int colFin) {
    swap(mat[0][colDeb],mat[0][colFin]);
    swap(mat[1][colDeb],mat[1][colFin]);
}

void posit(int col) {
    if (mat[0][col]<0) {
        mat[0][col]*=-1;
        mat[1][col]*=-1;
    }
}

void modif(int colModif,int colAj,int coeff) {
    mat[0][colModif]+=coeff*mat[0][colAj];
    mat[1][colModif]+=coeff*mat[1][colAj];
    if (pgcd!=0) {
        mat[1][colModif]%=pgcd;
    }
}

void calc(int colDeb,int colFin) {
    posit(colDeb);
    posit(colFin);
    //afficher();
    if (mat[0][colDeb]<mat[0][colFin]) {
        echange(colDeb,colFin);
    }
    //afficher();
    while (mat[0][colFin]!=0) {
        modif(colDeb,colFin,-mat[0][colDeb]/mat[0][colFin]);
        echange(colDeb,colFin);
        //afficher();
    }
    if (mat[1][colFin]!=0) {
        mat[1][colFin]=abs(mat[1][colFin]);
        if (pgcd==0) {
            pgcd=mat[1][colFin];
        }
        else {
            pgcd=gcd(pgcd,mat[1][colFin]);
        }
    }
}

/*int pgcd(vector<int> v) {
    int ans=v[0];
    for (int i=1;i<(int)v.size();i++) {
        ans=gcd(ans,v[i]);
    }
    return ans;
}*/

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>nbPort;
    cin>>colPrem>>ligPrem;
    if (nbPort<=2) {
        cout<<-1<<endl;
        return 0;
    }
    int colNouv,ligNouv;
    for (int i=0;i<nbPort-1;i++) {
        cin>>colNouv>>ligNouv;
        mat[0][i]=ligNouv-ligPrem;
        mat[1][i]=colNouv-colPrem;
    }
    //afficher();
    for (int i=1;i<nbPort-1;i++) {
        calc(0,i);
        //afficher();
    }
    int rep=pgcd*mat[0][0];
    if (rep==0) {
        cout<<-1<<endl;
    }
    else {
        cout<<abs(rep)<<endl;
    }
    return 0;
}
  

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