Submission #1215435

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215435		thelegendary08	Fountain Parks (IOI21_parks)	C++17	15 / 100	58 ms	13880 KiB

parks

#include "parks.h"
#include<bits/stdc++.h>
#define vi vector<int>
#define f0r(i,n) for(int i = 0; i<n; i++)
#define mp make_pair
#define pb push_back
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define pii pair<int,int>
#define dout(x) cout<<x<<' '<<#x<<'\n';
#define vout(x) for(auto u : x)cout<<u<<' '; cout<<'\n';
#define vvi vector<vi>

using namespace std;
const int mxn = 1e5 +5;
int construct_roads(std::vector<int> x, std::vector<int> y) {
	vector<vector<int>>grid(2, vi(mxn, -1));
	int n = x.size();
	f0r(i,n){
		int a = x[i] / 2 - 1;
		int b = y[i] / 2 - 1;
		grid[a][b] = i;
	}
	int fi = -1;
	f0r(i, mxn){
		if(grid[0][i] != -1 || grid[1][i] != -1){
			fi = i; break;
		}
	}
	
	int done = 0;
	vi u,v,a,b;
	if(grid[0][fi] != -1 && grid[1][fi] != -1){
		u.pb(grid[0][fi]); v.pb(grid[1][fi]); a.pb(3); b.pb(fi * 2 + 1);
	}
	done += (grid[0][fi] != -1) + (grid[1][fi] != -1);
	bool ok = 1;
	FOR(i, fi + 1, mxn){
		if(done == n)break;
		if(grid[0][i] == -1 && grid[1][i] == -1){
			ok = 0;
			break;
		}
		if(grid[0][i] == -1 && grid[1][i] != -1 && grid[0][i-1] != -1 && grid[1][i-1] == -1){
			ok = 0; break;
		}
		if(grid[0][i] != -1 && grid[1][i] == -1 && grid[0][i-1] == -1 && grid[1][i-1] != -1){
			ok = 0; break;
		}
		if(grid[0][i] != -1 && grid[0][i-1] != -1){
			u.pb(grid[0][i]);v.pb(grid[0][i-1]);a.pb(1);b.pb(i * 2 + 1);
		}
		if(grid[1][i] != -1 && grid[1][i-1] != -1){
			u.pb(grid[1][i]); v.pb(grid[1][i-1]); a.pb(5); b.pb(i * 2 + 1);
		}
		int lef = (grid[0][i-1] != -1) + (grid[1][i-1] != -1);
		int rig = (grid[0][i] != -1) + (grid[1][i] != -1);
		if(lef == 1 && rig == 2){
			u.pb(grid[0][i]); v.pb(grid[1][i]); a.pb(3); b.pb(i * 2 + 1);
		}
		done += (grid[0][i] != -1) + (grid[1][i] != -1);
	}
	if(!ok)return 0;
	build(u,v,a,b);
	return 1;
	
	/*
    if (x.size() == 1) {
	build({}, {}, {}, {});
        return 1;
    }
    std::vector<int> u, v, a, b;
    u.push_back(0);
    v.push_back(1);
    a.push_back(x[0]+1);
    b.push_back(y[0]-1);
    build(u, v, a, b);
    return 1;
    */
}

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