제출 #385787

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
385787		mohamedsobhi777	Triangles (CEOI18_tri)	C++14	20 / 100	2 ms	512 KiB

tri

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

#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int, int>>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define loop(_) for (int __ = 0; __ < (_); ++__)
#define pb push_back
#define f first
#define s second
#define sz(_) ((int)_.size())
#define all(_) _.begin(), _.end()
#define lb lower_bound
#define ub upper_bound

using ll = long long;
using ld = long double;

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

int gn;
int ans;

bool ok(int x, int y)
{
       int mask = 0;
       for (int i = 1; i <= gn; ++i)
       {
              if (x == i || y == i || mask == 3)
                     continue;
              mask |= 1 << is_clockwise(x, y, i);
       }
       return mask != 3;
}

// int solve(vi v)
// {
//        if (sz(v) == 0)
//               return 0;
//        if (sz(v) == 1)
//               return 2;
//        vi lhs, rhs;
//        random_shuffle(all(v));
//        int x = v[0], y = v[1];
//        for (int i = 2; i < sz(v); ++i)
//        {
//               int z = v[i];
//               (is_clockwise(x, y, z) ? lhs : rhs).pb(z);
//        }
//        return 2 + solve(lhs) + solve(rhs);
// }

int vis[N];

void dfs(int x)
{
       vis[x] = 1;

       for (int i = 1; i <= gn; ++i)
       {
              if (vis[i])
                     continue;
              if (ok(x, i))
              {
                     ++ans;
                     dfs(i);
                     break;
              }
       }
}

int main()
{
       ios_base::sync_with_stdio(0);
       cin.tie(0);
#ifndef ONLINE_JUDGE
#endif
       gn = get_n();
       set<int> st;
       for (int i = 2; i <= gn; ++i)
       {
              st.insert(i);
       }

       while (sz(st) > 1)
       {
              vi v;
              for (auto u : st)
              {
                     v.pb(u);
              }
              random_shuffle(all(v));
              int t = v.back();
              vi lhs = {t}, rhs;
              for (auto u : v)
              {
                     if (u == t)
                            continue;
                     if (!is_clockwise(1, t, u))
                     {
                            lhs.pb(u);
                     }
              }
              st.clear();
              for (auto u : lhs)
                     st.insert(u);
       }

       int root = *st.begin();
       bool flag = 0;
       for (int i = 1; i <= gn; ++i)
       {
              if (i == root)
                     continue;
              flag |= ok(i, root);
       }
       assert(flag);
       dfs(root);
       cout << ++ans;
       return 0;
}

• Subtask 1: 0 / 15
• Subtask 2: 0 / 20
• Subtask 3: 0 / 20
• Subtask 4: 20 / 20
• Subtask 5: 0 / 25