Submission #1095066

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095066		alexander707070	Triangles (CEOI18_tri)	C++14	0 / 100	1 ms	348 KiB

tri

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

#define MAXN 100007
using namespace std;

int n;

/*static long long *x, *y;
static int queries=0;

static void init() {
	static int is_inited=0;
	if (is_inited)
		return;
	is_inited=1;
	assert(scanf("%d", &n)==1);
	x=(long long*)malloc((n+1)*sizeof(long long));
	y=(long long*)malloc((n+1)*sizeof(long long));
	for (int i=1; i<=n; i++){
        x[i]=rand()%100+1;
        y[i]=rand()%100+1;

		//assert(scanf("%lld%lld", &x[i], &y[i])==2);
    }
}

int get_n() {
	init();
	return n;
}

int is_clockwise(int a, int b, int c) {
	init();
	assert(a>=1 && a<=n);
	assert(b>=1 && b<=n);
	assert(c>=1 && c<=n);
	assert(a!=b && a!=c && b!=c);
	queries++;
        if(queries == 1000 * 1000 + 1)
            printf("Too many queries!");
	return (x[b]-x[a])*(y[c]-y[a])-(x[c]-x[a])*(y[b]-y[a])<0;
}

void give_answer(int s) {
	init();
	printf("%d\n", s);
}*/

vector<int> combine(vector<int> a,vector<int> b){
    if(a.empty())return b;
    if(b.empty())return a;

    for(int test=0;test<200;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()>=3 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) or test==199){
            if(b1 and b2){
                exit(0);
            }
            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(w[r1],w[i],w[r2]))l.push_back(w[i]);
        else r.push_back(w[i]);
    }

    vector<int> convL=solve(l);
    vector<int> convR=solve(r);

    vector<int> sol=combine(convL,{w[r1],w[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:59:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for(int i=pos;i<a.size();i++)res.push_back(a[i]);
      |                       ~^~~~~~~~~
tri.cpp:64:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(int i=pos2;i<b.size();i++){
      |                        ~^~~~~~~~~
tri.cpp:83:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |         for(int i=0;i<res.size();i++){
      |                     ~^~~~~~~~~~~
tri.cpp: In function 'std::vector<int> solve(std::vector<int>)':
tri.cpp:132:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  132 |     for(int i=0;i<w.size();i++){
      |                 ~^~~~~~~~~
tri.cpp: In function 'std::vector<int> combine(std::vector<int>, std::vector<int>)':
tri.cpp:111:1: warning: control reaches end of non-void function [-Wreturn-type]
  111 | }
      | ^

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