Submission #1095328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1095328		alexander707070	Triangles (CEOI18_tri)	C++14	100 / 100	378 ms	7740 KiB

tri

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

#define MAXN 200007
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);
}*/

bool cmp(int x,int y){
    return is_clockwise(1,x,y);
}

vector<int> l,r,res;
int s[MAXN],ss[MAXN],cnt[MAXN],sol;
map< pair<int,pair<int,int> > , int > mp;

void shift(int x){
    for(int i=1;i<=n;i++){
        if(i+x<=n)ss[i+x]=s[i];
        else ss[i+x-n]=s[i];
    }

    for(int i=1;i<=n;i++)s[i]=ss[i];
}

bool check(int x,int y,int z){
    if(mp[{x,{y,z}}]>0)return mp[{x,{y,z}}]-1;
    
    mp[{x,{y,z}}]=is_clockwise(x,y,z);
    mp[{x,{y,z}}]++;

    return mp[{x,{y,z}}]-1;
}

int main(){

    srand(42069);

    n=get_n();

    for(int i=2;i<=n-1;i++){
        if(!is_clockwise(1,n,i)){
            l.push_back(i);
        }else{
            r.push_back(i);
        }
    }

    sort(l.begin(),l.end(),cmp);
    sort(r.begin(),r.end(),cmp);

    s[1]=1;
    for(int i=0;i<l.size();i++){
        s[i+2]=l[i];
    }

    s[l.size()+2]=n;

    for(int i=0;i<r.size();i++){
        s[l.size()+3+i]=r[i];
    }

    for(int test=1;test<=20;test++){
        res.clear();
        shift(rand()%n);

        for(int i=1;i<=n;i++){
            while(res.size()>=2 and !check(res[res.size()-2],res[res.size()-1],s[i])){
                res.pop_back();
            }

            res.push_back(s[i]);
        }

        for(int i:res)cnt[i]++;
    }

    for(int i=1;i<=n;i++){
        if(cnt[i]==20)sol++;
    }

    give_answer(sol);

    return 0;
}

Compilation message (stderr)

tri.cpp: In function 'int main()':
tri.cpp:95:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int i=0;i<l.size();i++){
      |                 ~^~~~~~~~~
tri.cpp:101:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(int i=0;i<r.size();i++){
      |                 ~^~~~~~~~~

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