제출 #826151

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
826151		Khizri	Triangles (CEOI18_tri)	C++17	0 / 100	0 ms	300 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;
void solve(){
    n=get_n();
    vector<int>vt(n);
    iota(all(vt),1);
    int node=0;
    while(1){
        //cout<<vt.size()<<endl;
        vector<int>que;
        while(que.size()<2){
            int idx=rng()%vt.size();
            int x=vt[idx];
            bool ok=true;
            for(int q:que){
                if(q==x) ok=false;
            }
            if(ok){
                que.pb(x);
            }
        }
        vector<int>nw;
        for(int i=0;i<vt.size();i++){
            if(vt[i]==que[0]||vt[i]==que[1]) continue;
            int res=is_clockwise(que[0],que[1],vt[i]);
            if(res==0){
                nw.pb(vt[i]);
            }
        }
        if(nw.size()==0){
            node=que[0];
            break;
        }
        vt=nw;
        vt.pb(que[0]);
        vt.pb(que[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 
*/

컴파일 시 표준 에러 (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:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for(int i=0;i<vt.size();i++){
      |                     ~^~~~~~~~~~
tri.cpp:98:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |             for(int i=0;i<vt.size();i++){
      |                         ~^~~~~~~~~~

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