Submission #1095301

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095301		alexander707070	Triangles (CEOI18_tri)	C++14	55 / 100	1174 ms	1964 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;
        //cin>>x[i]>>y[i];

		//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);
}*/

int li[MAXN],tim;

bool check(int x,int y,vector<int> w){
    if(x==y)return false;

    for(int i:w){
        if(i==x or i==y)continue;

        if(is_clockwise(x,i,y))return false;
    }

    return true;
}

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

    deque<int> l,r;
    vector<int> res,c;

    c=a;
    for(int i:b)c.push_back(i);

    tim++;
    int pos=0;
    for(int i=0;i<a.size();i++){
        if(check(a[i],a[(i+1)%a.size()],b)){
            l.push_back(i);
        }
    }

    while(!l.empty() and (l.back()+1)%a.size()==l.front()){
        l.push_back(l.front());
        l.pop_front();
    }

    tim++;
    for(int i=0;i<b.size();i++){
        if(check(b[i],b[(i+1)%b.size()],a)){
            r.push_back(i);
        }
    }

    while(!r.empty() and (r.back()+1)%b.size()==r.front()){
        r.push_back(r.front());
        r.pop_front();
    }

    for(int i=0;i<l.size();i++){
        if(i==0){
            res.push_back(a[l[i]]);
            res.push_back(a[(l[i]+1)%a.size()]);
        }else{
            res.push_back(a[(l[i]+1)%a.size()]);
        }
    }

    for(int i=0;i<r.size();i++){
        if(i==0){
            res.push_back(b[r[i]]);
            res.push_back(b[(r[i]+1)%b.size()]);
        }else{
            res.push_back(b[(r[i]+1)%b.size()]);
        }
    }

    for(int i=0;i<l.size();i++)l[i]=a[l[i]];
    for(int i=0;i<r.size();i++)r[i]=b[r[i]];

    if(l.empty()){
        for(int i:a){
            if(check(i,res.front(),c) and check(res.back(),i,c)){
                res.push_back(i); break;
            }
        }

        return res;
    }

    if(r.empty()){
        for(int i:b){
            if(check(i,res.front(),c) and check(res.back(),i,c)){
                res.push_back(i); break;
            }
        }

        return res;
    }

    if(res.size()>2 and !is_clockwise(res[0],res[1],res[2]))reverse(res.begin(),res.end());

    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;
    }

    vector<int> sol;

    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);

    sol=combine(convL,{w[r1],w[r2]});
    sol=combine(sol,convR);    

    return sol;
}

vector<int> perm;

int main(){

    srand(42069);

    n=get_n();

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

    vector<int> res=solve(perm);
    
    give_answer(res.size());
    //for(int i:res)cout<<i<<" ";

    //cout<<queries<<"\n";

    return 0;
}

Compilation message (stderr)

tri.cpp: In function 'std::vector<int> combine(std::vector<int>, std::vector<int>)':
tri.cpp:77:18: 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<a.size();i++){
      |                 ~^~~~~~~~~
tri.cpp:83:47: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   83 |     while(!l.empty() and (l.back()+1)%a.size()==l.front()){
      |                          ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
tri.cpp:89:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i=0;i<b.size();i++){
      |                 ~^~~~~~~~~
tri.cpp:95:47: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} [-Wsign-compare]
   95 |     while(!r.empty() and (r.back()+1)%b.size()==r.front()){
      |                          ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
tri.cpp:100:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for(int i=0;i<l.size();i++){
      |                 ~^~~~~~~~~
tri.cpp:109:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for(int i=0;i<r.size();i++){
      |                 ~^~~~~~~~~
tri.cpp:118:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  118 |     for(int i=0;i<l.size();i++)l[i]=a[l[i]];
      |                 ~^~~~~~~~~
tri.cpp:119:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  119 |     for(int i=0;i<r.size();i++)r[i]=b[r[i]];
      |                 ~^~~~~~~~~
tri.cpp:76:9: warning: unused variable 'pos' [-Wunused-variable]
   76 |     int pos=0;
      |         ^~~
tri.cpp: In function 'std::vector<int> solve(std::vector<int>)':
tri.cpp:167:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  167 |     for(int i=0;i<w.size();i++){
      |                 ~^~~~~~~~~
tri.cpp: At global scope:
tri.cpp:10:12: warning: 'queries' defined but not used [-Wunused-variable]
   10 | static int queries=0;
      |            ^~~~~~~
tri.cpp:9:23: warning: 'y' defined but not used [-Wunused-variable]
    9 | static long long *x, *y;
      |                       ^
tri.cpp:9:19: warning: 'x' defined but not used [-Wunused-variable]
    9 | static long long *x, *y;
      |                   ^

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