oj.uz

답안 #359635

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
359635 2021-01-27T05:54:31 Z mohamedsobhi777 Building Skyscrapers (CEOI19_skyscrapers) C++14
0 / 100
 394 ms 30588 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#pragma GCC optimize("-Ofast")
//#pragma GCC optimize("trapv")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.2,popcnt,abm,mmx,avx2,tune=native")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-funroll-loops")

using namespace std;
using namespace __gnu_pbds;

#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define vvi vector<vi>
#define vvii vector<vii>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define forn(i, n) for (int i = 0; i < n; ++i)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define uni(_) unique(_)
#define lb lower_bound
#define ub upper_bound
#define si set<int>
#define ms multiset<int>
#define qi queue<int>
#define pq prioriry_queue<int>
#define mi map<int, int>
#define inc(i, l, r) for (int i = l; i <= r; i++)
#define dec(i, l, r) for (int i = l; i >= r; i--)

using lll = __int128;
using ll = long long;
using ld = long double;

const int N = 2e5 + 7;
const ll mod = 1e9 + 7;
const ll inf = 2e18;

auto ra = [] {char *p = new char ; delete p ; return ll(p) ; };
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count() * (ra() | 1));
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> os;

int n;
vii a;
vii A;

struct dsu
{
       int fat[N];
       int combo = 0;
       dsu()
       {
              iota(fat, fat + N, 0);
       }
       int find(int x) { return fat[x] = (fat[x] == x ? x : find(fat[x])); }
       void link(int u, int v)
       {
              u = find(u);
              v = find(v);
              if (u != v)
                     fat[u] = v, combo--;
       }
} de;

bool chk()
{
       de.combo = n;
       map<pair<int, int>, int> rak;
       for (int i = 0; i < n; ++i)
              rak[A[i]] = i + 1;

       for (auto u : A)
       {
              inc(j, -1, 1) inc(k, -1, 1)
              {
                     pii c = {u.f + j, u.s + k};
                     if (rak[c])
                     {
                            de.link(rak[c], rak[u]);
                     }
              }
       }
       return de.combo == 1;
}

int main()
{
       ios_base::sync_with_stdio(0);
       cin.tie(0);
#ifndef ONLINE_JUDGE
#endif
       cin >> n;
       int t;
       cin >> t;
       map<int, vi> mp;
       for (int i = 0; i < n; ++i)
       {
              int x, y;
              cin >> x >> y;
              mp[x + y].pb(i);
              //              a.pb({x + y, i + 1});
              A.pb({x, y});
       }
       map<pii, bool> hasm;

       auto hasn = [&](int x, int y) -> bool {
              inc(j, -1, 1) inc(k, -1, 1)
              {
                     pii c = {x + j, y + k};
                     if (hasm[c])
                     {
                            return 1;
                     }
              }
              return 0;
       };

       if (chk())
       {
              vi ans;
              { // t = 1
                     int cnt = 0;
                     for (auto it : mp)
                     {
                            set<int> st;
                            for (auto u : it.s)
                                   st.insert(u);
                            while (sz(st))
                            {

                                   bool ok = 0;

                                   for (auto u : st)
                                   {
                                          if (hasn(A[u].f, A[u].s) || cnt == 0)
                                          {
                                                 hasm[{A[u].f, A[u].s}] = 1;
                                                 ans.pb(u);
                                                 st.erase(u);
                                                 ok = 1;
                                                 break;
                                          }
                                   }
                                   if (!ok)
                                   {
                                          return cout << "NO", 0;
                                   }
                            }
                            cnt++;
                     }
              }
              cout << "YES\n";
              for (auto u : ans)
                     cout << ++u << "\n";
       }
       else
       {
              cout << "NO";
       }
       return 0;
}

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1132 KB ans=YES N=1
2 Correct 1 ms 1132 KB ans=YES N=4
3 Correct 1 ms 1132 KB ans=NO N=4
4 Correct 1 ms 1132 KB ans=YES N=5
5 Correct 1 ms 1132 KB ans=YES N=9
6 Correct 1 ms 1132 KB ans=YES N=5
7 Correct 1 ms 1132 KB ans=NO N=9
8 Correct 1 ms 1132 KB ans=NO N=10
9 Correct 1 ms 1132 KB ans=YES N=10
10 Correct 1 ms 1132 KB ans=YES N=10
11 Incorrect 1 ms 1132 KB Full cells must be connected
12 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1132 KB ans=YES N=1
2 Correct 1 ms 1132 KB ans=YES N=4
3 Correct 1 ms 1132 KB ans=NO N=4
4 Correct 1 ms 1132 KB ans=YES N=5
5 Correct 1 ms 1132 KB ans=YES N=9
6 Correct 1 ms 1132 KB ans=YES N=5
7 Correct 1 ms 1132 KB ans=NO N=9
8 Correct 1 ms 1132 KB ans=NO N=10
9 Correct 1 ms 1132 KB ans=YES N=10
10 Correct 1 ms 1132 KB ans=YES N=10
11 Incorrect 1 ms 1132 KB Full cells must be connected
12 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1132 KB ans=YES N=1
2 Correct 1 ms 1132 KB ans=YES N=4
3 Correct 1 ms 1132 KB ans=NO N=4
4 Correct 1 ms 1132 KB ans=YES N=5
5 Correct 1 ms 1132 KB ans=YES N=9
6 Correct 1 ms 1132 KB ans=YES N=5
7 Correct 1 ms 1132 KB ans=NO N=9
8 Correct 1 ms 1132 KB ans=NO N=10
9 Correct 1 ms 1132 KB ans=YES N=10
10 Correct 1 ms 1132 KB ans=YES N=10
11 Incorrect 1 ms 1132 KB Full cells must be connected
12 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 2412 KB ans=NO N=1934
2 Correct 6 ms 1644 KB ans=NO N=1965
3 Incorrect 6 ms 1260 KB Contestant did not find solution
4 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 1132 KB ans=YES N=1
2 Correct 1 ms 1132 KB ans=YES N=4
3 Correct 1 ms 1132 KB ans=NO N=4
4 Correct 1 ms 1132 KB ans=YES N=5
5 Correct 1 ms 1132 KB ans=YES N=9
6 Correct 1 ms 1132 KB ans=YES N=5
7 Correct 1 ms 1132 KB ans=NO N=9
8 Correct 1 ms 1132 KB ans=NO N=10
9 Correct 1 ms 1132 KB ans=YES N=10
10 Correct 1 ms 1132 KB ans=YES N=10
11 Incorrect 1 ms 1132 KB Full cells must be connected
12 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 367 ms 8672 KB ans=NO N=66151
2 Correct 394 ms 30588 KB ans=NO N=64333
3 Incorrect 365 ms 6624 KB Contestant did not find solution
4 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 2412 KB ans=NO N=1934
2 Correct 6 ms 1644 KB ans=NO N=1965
3 Incorrect 6 ms 1260 KB Contestant did not find solution
4 Halted 0 ms 0 KB -