Submission #346391

#	Time	Username	Problem	Language	Result	Execution time	Memory
346391		doowey	Building Skyscrapers (CEOI19_skyscrapers)	C++14	0 / 100	193 ms	15328 KiB

skyscrapers

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int dir[8][2] = {{-1,-1},{-1,0},{-1,+1},{0,-1},{0,+1},{1,-1},{1,0},{1,+1}};

map<pii,int> indx;
map<pii,bool> vis;
int cnt;

void dfs(pii go){
    pii nx;
    vis[go]=true;
    cnt ++ ;
    for(int d = 0 ; d < 8 ; d ++ ){
        nx = mp(go.fi + dir[d][0], go.se + dir[d][1]);
        if(indx.count(nx)){
            if(!vis.count(nx)){
                dfs(nx);
            }
        }
    }
}

int main(){
    fastIO;
    int n;
    cin >> n;
    int typ;
    cin >> typ;
    pii cc;
    vector<pii> ass;
    for(int i = 1; i <= n; i ++ ){
        cin >> cc.fi >> cc.se;
        indx[cc]=i;
        ass.push_back(cc);
    }
    sort(ass.begin(), ass.end());
    dfs(ass[0]);
    if(cnt != n){
        cout << "NO\n";
        return 0;
    }
    cout << "YES\n";
    for(int i = n - 1; i >= 0 ; i -- ){
        cout << indx[ass[i]] << " ";
    }
    cout << "\n";
    return 0;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 14
• Subtask 3: 0 / 12
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20
• Subtask 6: 0 / 10
• Subtask 7: 0 / 19