Submission #826219

#	Time	Username	Problem	Language	Result	Execution time	Memory
826219		Khizri	Triangles (CEOI18_tri)	C++17	20 / 100	1 ms	292 KiB

tri

#include "trilib.h"
#include <bits/stdc++.h>
using namespace std;
//------------------------------DEFINE------------------------------
//******************************************************************
#define IOS ios_base::sync_with_stdio(false); cin.tie(0),cout.tie(0)
#define ll unsigned long long
#define pb push_back
#define F first
#define S second
#define INF 1e18
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define OK cout<<"Ok"<<endl;
#define MOD (ll)(1e9+7)
#define endl "\n"
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//******************************************************************
//----------------------------FUNCTION------------------------------
//******************************************************************
ll gcd(ll a,ll b){
    if(a>b) swap(a,b);
    if(a==0) return a+b;
    return gcd(b%a,a);
}
ll lcm(ll a,ll b){
    return a/gcd(a,b)*b;
}
bool is_prime(ll n){
    ll k=sqrt(n);
 
    if(n==2) return true;
    if(n<2||n%2==0||k*k==n) return false;
    for(int i=3;i<=k;i+=2){
        if(n%i==0){
            return false;
        }
    }
    return true;
}
//*****************************************************************
//--------------------------MAIN-CODE------------------------------
const int mxn=2e5+5;
int t=1,n;
map<pair<int,pii>,int>mp;
void solve(){
    n=get_n();
    int a=1,b=2;
    for(int i=3;i<=n;i++){
        int res=is_clockwise(a,b,i);
        if(res==1){
            b=i;
        }
    }
    int node=b;
    //if(is_clockwise(2,b,1)){
        //node=1;
    //}
    set<int>st;
    st.insert(node);
    bool ok=true;
    //cout<<node<<endl;
    while(ok){
        //cout<<node<<endl;
        vector<int>vt(n);
        iota(all(vt),1);
        while(vt.size()>1){
            int x=0;
            while(1){
                int idx=rng()%((int)vt.size());
                x=vt[idx];
                if(x!=node) break;
            }
            vector<int>nw;
            for(int i=0;i<vt.size();i++){
                if(node==vt[i]||x==vt[i]) continue;
                int res=is_clockwise(node,x,vt[i]);
                if(res==0){
                    nw.pb(vt[i]);
                }
            }
            if(nw.size()==0){
                node=x;
                if(!st.count(node)){
                    st.insert(node);
                }
                else{
                    ok=false;
                }
                break;
            }
            else if(nw.size()==1){
                node=nw[0];
                if(!st.count(node)){
                    st.insert(node);
                }
                else{
                    ok=false;
                }
                break;
            }
            vt=nw;
        }
    }
    int ans=st.size();
    give_answer(ans);
}
int main(){
    //IOS;
    //cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
/*
g++ tri.cpp trilib.c ; .\a.exe 
9
1 1 
4 3 
2 2 
1 4
5 1 
3 2
0 0
1000 0 
0 1000
 
6
0 0 
1 -1
2 0
0 1 
-1 2 
0 3 
*/

Compilation message (stderr)

tri.cpp: In function 'bool is_prime(long long unsigned int)':
tri.cpp:36:18: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   36 |     for(int i=3;i<=k;i+=2){
      |                 ~^~~
tri.cpp: In function 'void solve()':
tri.cpp:77:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   77 |             for(int i=0;i<vt.size();i++){
      |                         ~^~~~~~~~~~

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