Submission #826444

#	Time	Username	Problem	Language	Result	Execution time	Memory
826444		joelgun14	Triangles (CEOI18_tri)	C++17	100 / 100	35 ms	4268 KiB

tri

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include "trilib.h"
using namespace std;
using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
int qcnt = 0;
//gp_hash_table<long long, int> memo;
//gp_hash_table<long long, bool> vis;
//long long const1 = 16e8, const2 = 4e4, const3 = 1;
int get_query(int x, int y, int z) {
    //if(vis[const1 * x + const2 * y + const3 * z])
    //    return memo[const1 * x + const2 * y + const3 * z];
    //assert(x != y && y != z && x != z);
    //++qcnt;
    //assert(qcnt <= 1e6);
    // coba pastiin ini sebenernya udah sampe mana sih, harusnya udh close to finished
    //vis[const1 * x + const2 * y + const3 * z] = 1;
    return is_clockwise(x, y, z);
}
deque<int> solve(deque<int> a) {
    // a itu yg kita mau solve skrg
    // pick 2 random variables, terus nnti cek semuanya ada di kiri/kanannya a
    //assert(a.size() >= 2);
    if(a.size() == 1) {
        return a;
    }
    else if(a.size() == 2) {
        // any is correct
        return a;
    }
    else if(a.size() == 3) {
        // coba aja urutan mana yg clockwise
        if(get_query(a[0], a[1], a[2]))
            return a;
        else {
            swap(a[0], a[1]);
            //assert(get_query(a[0], a[1], a[2]));
            return a;
        }
    }
    else {
        // pick 2 random, terus nnti dipisah
        int x = rng() % a.size(), y;
        do {    
            y = rng() % a.size();
        } while(x == y);
        x = a[x], y = a[y];
        //assert(x != y);
        deque<int> g1, g2;
        // do random sampai ketemu yg mendekati /2
        for(auto i : a) {
            if(i == x || i == y)
                continue;
            if(get_query(x, y, i))
                g1.push_back(i);
            else
                g2.push_back(i);
        }
        g1.push_back(y);
        g2.push_back(x);
        g1 = solve(g1);
        g2 = solve(g2);
        // combine g1 and g2
        // jadiin g1, g2 jadi bentuk yg diinginkan
        // g1
        // y ... x
        // g2
        // x ... y
        //cout << "ENTER G1" << endl;
        while(g1.front() != y) {
            g1.push_front(g1.back());
            g1.pop_back();
        }
        while(g2.front() != x) {
            g2.push_front(g2.back());
            g2.pop_back();
        }
        //assert(g1.front() == y && g1.back() == x);
        //assert(g2.front() == x && g2.back() == y);
        //cout << "PART1" << endl;
        while(g1.size() >= 2 || g2.size() >= 2) {
            bool change = 0;
            //cout << x << " " << y << endl;
            //for(auto i : g1)
            //    cout << i << " ";
            //cout << endl;
            //for(auto i : g2) {
            //    cout << i << " ";
            //}
            //cout << endl;
            if(g1.size() == 1) {
                // coba hapus g2
                //cout << "TEST HERE" << endl;
                if(!get_query(g1.back(), g2.front(), g2[1]))
                    g2.pop_front(), change = 1;
            }
            else if(g2.size() == 1) {
                // coba hapus g1
                //cout << "TEST2" << endl;
                if(!get_query(g1[g1.size() - 2], g1.back(), g2[0]))
                    g1.pop_back(), change = 1;
            }
            else {
                // bisa coba hapus dua"nya
                //cout << "LAST CASE" << endl;
                if(!get_query(g1.back(), g2.front(), g2[1]))
                    g2.pop_front(), change = 1;
                else if(!get_query(g1[g1.size() - 2], g1.back(), g2[0]))
                    g1.pop_back(), change = 1;
            }
            if(!change)
                break;
        }
        //cout << "PART2" << endl;
        while(g1.size() >= 2 || g2.size() >= 2) {
            //cout << x << " " << y << endl;
            //for(auto i : g1)
            //    cout << i << " ";
            //cout << endl;
            //for(auto i : g2) {
            //    cout << i << " ";
            //}
            //cout << endl;
            bool change = 0;
            if(g2.size() == 1) {
                //cout << "TEST2" << endl;
                // coba hapus g2
                if(!get_query(g2.back(), g1.front(), g1[1]))
                    g1.pop_front(), change = 1;
            }
            else if(g1.size() == 1) {
                //cout << "TEST3" << endl;
                // coba hapus g1
                if(!get_query(g2[g2.size() - 2], g2.back(), g1[0]))
                    g2.pop_back(), change = 1;
            }
            else {
                // bisa coba hapus dua"nya
                //cout << "TEST4" << endl;
                if(!get_query(g2.back(), g1.front(), g1[1]))
                    g1.pop_front(), change = 1;
                else if(!get_query(g2[g2.size() - 2], g2.back(), g1[0]))
                    g2.pop_back(), change = 1;
            }
            if(!change)
                break;
        }
        //cout << "PART 2 OVER" << endl;
        deque<int> ret;
        for(auto i : g1)
            ret.push_back(i);
        for(auto i : g2) {
            ret.push_back(i);
        }
        //cout << "OTW RETURN" << endl;
        //cout << s.size() << " " << ret.size() << endl;
        //assert(s.size() == ret.size());
        return ret;
    }
}
int main() {
    int n;
    n = get_n();
    deque<int> v;
    for(int i = 1; i <= n; ++i)
        v.push_back(i);
    v = solve(v);
    //cout << v.size() << endl;
    //for(int i = 0; i < v.size(); ++i) {
    //    //assert(get_query(v[i], v[(i + 1) % v.size()], v[(i + 2) % v.size()]));
    //}
    // pastikan v unique?
    give_answer(v.size());
    return 0;
}

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