| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 300545 | daniel920712 | Carnival Tickets (IOI20_tickets) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "plants.h"
#include <stdio.h>
#include <vector>
#include <utility>
using namespace std;
vector < pair < int , int > > con[200005];
vector < int > all;
vector < int > Next[200005];
int N,tt=0;
bool use[2000005];
void init(int k,vector<int> r)
{
int a=0,b=0,i,j,ok=0;
all=r;
N=r.size();
if(k==2) tt=1;
for(i=0;i<N;i++)
{
if(k==2)
{
if(r[(i+N-1)%N]!=r[i])
{
b=0;
a++;
con[i].push_back(make_pair(a,0));
for(j=(i+1)%N;r[(j+N-1)%N]==r[i];j=(j+1)%N)
{
if(j==N-1) ok=1;
if(r[i]==0) b--;
else b++;
con[j].push_back(make_pair(a,b));
}
}
}
if(r[i]==k-1) for(j=1;j<k;j++) Next[j].push_back((j+1)%N);
if(r[i]==0) for(j=1;j<k;j++) Next[(j+i)%N].push_back(j);
if(r[i]>r[(i+1)%N]) Next[i].push_back((i+1)%N);
if(r[i]<r[(i+1)%N]) Next[(i+1)%N].push_back(i);
}
return;
}
bool F(int a,int b)
{
if(a==b) return 1;
if(use[a]) return 0;
use[a]=1;
for(auto i:Next[a]) if(F(i,b)) return 1;
return 0;
}
int compare_plants(int x, int y)
{
int i;
if(tt)
{
for(auto i:con[x])
{
for(auto j:con[y])
{
if(i.first==j.first)
{
if(i.second<j.second) return -1;
return 1;
}
}
}
}
else
{
for(i=0;i<N;i++) use[i]=0;
if(F(x,y)) return -1;
else if(F(y,x)) return 1;
}
return 0;
}