Submission #1095042

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095042		alexander707070	Triangles (CEOI18_tri)	C++14	Compilation error	0 ms	0 KiB

tri

#include <bits/stdc++.h>
#include "trilib.h"

#define MAXN 100007
using namespace std;

int n;

vector<int> combine(vector<int> a,vector<int> b){
    for(int test=0;test<10;test++){

        int pos=rand()%int(a.size());
        vector<int> res;

        for(int i=pos;i<a.size();i++)res.push_back(a[i]);
        for(int i=0;i<pos;i++)res.push_back(a[i]);

        int pos2=rand()%int(b.size());

        for(int i=pos2;i<b.size();i++){
            while(res.size()>=2 and !is_clockwise(res[res.size()-2],res[res.size()-1],b[i])){
                res.pop_back();
            }
            res.push_back(b[i]);
        }

        for(int i=0;i<pos2;i++){
            while(res.size()>=2 and !is_clockwise(res[res.size()-2],res[res.size()-1],b[i])){
                res.pop_back();
            }
            res.push_back(b[i]);
        }

        while(res.size()>=2 and !is_clockwise(res[res.size()-2],res[res.size()-1],a[pos])){
            res.pop_back();
        }

        bool b1=false,b2=false;
        for(int i=0;i<res.size();i++){

            for(int f:a){
                if(f==res[i] or f==res[(i+1)%res.size()])continue;

                b1=(b1 or is_clockwise(res[i],f,res[(i+1)%res.size()]));
                b2=(b2 or !is_clockwise(res[i],f,res[(i+1)%res.size()]));

                if(b1 and b2)break;
            }

            for(int f:b){
                if(f==res[i] or f==res[(i+1)%res.size()])continue;

                b1=(b1 or is_clockwise(res[i],f,res[(i+1)%res.size()]));
                b2=(b2 or !is_clockwise(res[i],f,res[(i+1)%res.size()]));

                if(b1 and b2)break;
            }
        }

        if(!(b1 and b2))return res;
    }

    return res;
}

vector<int> solve(vector<int> w){
    if(w.size()<=2)return w;

    if(w.size()==3){
        if(!is_clockwise(w[0],w[1],w[2])){
            swap(w[0],w[2]);
        }
        return w;
    }

    int r1=rand()%int(w.size());
    int r2=r1;
    while(r2==r1){
        r2=rand()%int(w.size());
    }

    vector<int> l,r;

    for(int i=0;i<w.size();i++){
        if(i==r1 or i==r2)continue;

        if(is_clockwise(r1,i,r2))l.push_back(i);
        else r.push_back(i);
    }

    vector<int> convl=solve(l);
    vector<int> convr=solve(r);

    vector<int> sol=combine(convl,{r1,r2});
    sol=combine(sol,convr);

    return sol;
}

vector<int> perm;

int main(){

    n=get_n();

    for(int i=1;i<=n;i++){
        perm.push_back(i);
    }

    vector<int> res=solve(perm);
    
    give_answer(res.size());

    return 0;
}

Compilation message (stderr)

tri.cpp: In function 'std::vector<int> combine(std::vector<int>, std::vector<int>)':
tri.cpp:15:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   15 |         for(int i=pos;i<a.size();i++)res.push_back(a[i]);
      |                       ~^~~~~~~~~
tri.cpp:20:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         for(int i=pos2;i<b.size();i++){
      |                        ~^~~~~~~~~
tri.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |         for(int i=0;i<res.size();i++){
      |                     ~^~~~~~~~~~~
tri.cpp:63:12: error: 'res' was not declared in this scope
   63 |     return res;
      |            ^~~
tri.cpp: In function 'std::vector<int> solve(std::vector<int>)':
tri.cpp:84:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int i=0;i<w.size();i++){
      |                 ~^~~~~~~~~