Submission #609689

#	Time	Username	Problem	Language	Result	Execution time	Memory
609689		Ozy	Fountain Parks (IOI21_parks)	C++17	70 / 100	1061 ms	91292 KiB

parks

#include "parks.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "

#define X first
#define Y second

map<pair<int,int>, int> mapa,id,bancas;
lli n,p;
stack<pair<lli,lli> > pila;
pair<lli,lli> act,nuevo,mitad;

vector<int> u,v,a,b;
lli dir[8] = {0,2,0,-2,2,0,-2,0};
bool continua;

void construye(int U, int V, int A, int B) {

    u.push_back(U);
    v.push_back(V);
    a.push_back(A);
    b.push_back(B);
}

//quitar varios logs si no da en tiempo
int construct_roads(std::vector<int> x, std::vector<int> y) {

    n = x.size();
    act = {x[0],y[0]};

    rep(i,0,n-1) {
        nuevo = {x[i],y[i]};
        mapa[nuevo] = 1;
        id[nuevo] = i;

        if (nuevo < act) act = nuevo;
    }

    pila.push(act);
    while (!pila.empty()) {

        act = pila.top();
        mapa[act] = 2;
        continua = false;

        rep(i,0,3){
            nuevo = act;
            nuevo.X += dir[i];
            nuevo.Y += dir[i+4];

            p = mapa[nuevo];
            if (p == 0 || p == 2) continue;

            mitad.X = (act.X + nuevo.X)/2;
            mitad.Y = (act.Y + nuevo.Y)/2;

            if (i&1) {
                //movimiento horizontal
                mitad.Y++;
                if (bancas[mitad] == 1) {
                    mitad.Y -= 2;
                    if (bancas[mitad] == 0) {
                        construye(id[act], id[nuevo], mitad.X, mitad.Y);
                        bancas[mitad] = 1;
                        pila.push(nuevo);
                        continua=true;
                        break;
                    }
                }

                mitad.Y -= 2;
                if (bancas[mitad] == 1) {
                    mitad.Y += 2;
                    if (bancas[mitad] == 0) {
                        construye(id[act], id[nuevo], mitad.X, mitad.Y);
                        bancas[mitad] = 1;
                        pila.push(nuevo);
                        continua=true;
                        break;
                    }
                }
            }
            else {
                //movimiento vertical
                mitad.X++;
                if (bancas[mitad] == 1) {
                    mitad.X -= 2;
                    if (bancas[mitad] == 0) {
                        construye(id[act], id[nuevo], mitad.X, mitad.Y);
                        bancas[mitad] = 1;
                        pila.push(nuevo);
                        continua=true;
                        break;
                    }
                }

                mitad.X -= 2;
                if (bancas[mitad] == 1) {
                    mitad.X += 2;
                    if (bancas[mitad] == 0) {
                        construye(id[act], id[nuevo], mitad.X, mitad.Y);
                        bancas[mitad] = 1;
                        pila.push(nuevo);
                        continua=true;
                        break;
                    }
                }
            }
        }
        if (continua) {
            n--;
            continue;
        }
        rep(i,0,3) {
            nuevo = act;
            nuevo.X += dir[i];
            nuevo.Y += dir[i+4];

            p = mapa[nuevo];
            if (p == 0 || p == 2) continue;

            mitad.X = (act.X + nuevo.X)/2;
            mitad.Y = (act.Y + nuevo.Y)/2;
            if (i&1) mitad.Y++;
            else mitad.X++;

            if (bancas[mitad] == 0) {
                construye(id[act], id[nuevo], mitad.X, mitad.Y);
                bancas[mitad] = 1;
                pila.push(nuevo);
                continua=true;
                break;
            }

            if (i&1) mitad.Y -= 2;
            else mitad.X -= 2;

            if (bancas[mitad] == 0) {
                construye(id[act], id[nuevo], mitad.X, mitad.Y);
                bancas[mitad] = 1;
                pila.push(nuevo);
                continua=true;
                break;
            }
        }

        if (continua) {
            n--;
            continue;
        }
        pila.pop();
    }

    if (n > 1) return 0;

    build(u,v,a,b);
    return 1;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 20 / 20
• Subtask 5: 20 / 20
• Subtask 6: 0 / 30