Submission #775888

#	Time	Username	Problem	Language	Result	Execution time	Memory
775888		Amylopectin	Ancient Books (IOI17_books)	C++14	12 / 100	1 ms	340 KiB

books

#include "books.h"
#include <vector>
#include <algorithm>
using namespace std;
const long long mxn = 4e6 + 10;
// const long long mxn = 20;
struct we
{
	long long le,ri;
};
bool cmp(const struct we &l,const struct we &r)
{
	return l.le < r.le;
}
struct we cyc[mxn] = {};
long long ta[mxn] = {},ru,u[mxn] = {};
long long fimi(long long l,long long r)
{
	if(l < r)
		return l;
	return r;
}
long long fima(long long l,long long r)
{
	if(l > r)
		return l;
	return r;
}
long long ab(long long l)
{
	if(l < 0)
		return -l;
	return l;
}
long long minimum_walk(std::vector<int> pp, int sta) 
{
	long long i,j,n = pp.size(),m,cn,cm,fn,fm,su = 0,fii,cou
	,ble = sta,bri = sta,cmi,cva,cri,cle,cl,cr;
	for(i=0; i<n; i++)
	{
		ta[i] = pp[i];
	}
	ru = 0;
	cyc[0] = {-1,n+1};
	for(i=0; i<n; i++)
	{
		if(u[i] == 0)
		{
			cn = i;
			cou = 1;
			cyc[ru] = {i,i};
			while(1)
			{
				// if(cn <= sta)
				// {
					cyc[ru].le = fimi(cyc[ru].le,cn);
				// }
				// else 
				// {
					cyc[ru].ri = fima(cyc[ru].ri,cn);
				// }
				u[cn] = 1;
				su += ab(cn - ta[cn]);
				cn = ta[cn];
				if(cn == i)
				{
					break;
				}
				cou ++;
			}
			if(cou == 1)
			{
				// cyc[ru] = {-1,n+1};
			}
			// else if(cyc[ru].le == -1)
			// {
			// 	bri = fima(bri,cyc[ru].ri);
			// 	cyc[ru] = {-1,n+1};
			// }
			// else if(cyc[ru].ri == n+1)
			// {
			// 	ble = fimi(ble,cyc[ru].le);
			// 	cyc[ru] = {-1,n+1};
			// }
			else 
			{
				ru ++;
				// cyc[ru] = {-1,n+1};
			}
		}
	}
	sort(cyc,cyc+ru,cmp);
	cva = 0;
	cr = 0;
	for(i=0; i<ru; i++)
	{
		if(cyc[i].le <= cr)
		{
			cr = fima(cyc[i].ri,cr);
		}
		else 
		{
			cva += cyc[i].le - cr;
		}
	}

	// cmi = n+1;
	// for(i=0; i<ru; i++)
	// {
	// 	if(cyc[i].ri <= bri)
	// 	{
	// 		break;
	// 	}
	// 	cmi = fimi(cmi,cyc[i].ri - ble);
	// 	ble = fimi(cyc[i].le,ble);
	// }
	// cmi = fimi(cmi,bri - ble);

	return su + cva * 2;
}

Compilation message (stderr)

books.cpp: In function 'long long int minimum_walk(std::vector<int>, int)':
books.cpp:37:14: warning: unused variable 'j' [-Wunused-variable]
   37 |  long long i,j,n = pp.size(),m,cn,cm,fn,fm,su = 0,fii,cou
      |              ^
books.cpp:37:30: warning: unused variable 'm' [-Wunused-variable]
   37 |  long long i,j,n = pp.size(),m,cn,cm,fn,fm,su = 0,fii,cou
      |                              ^
books.cpp:37:35: warning: unused variable 'cm' [-Wunused-variable]
   37 |  long long i,j,n = pp.size(),m,cn,cm,fn,fm,su = 0,fii,cou
      |                                   ^~
books.cpp:37:38: warning: unused variable 'fn' [-Wunused-variable]
   37 |  long long i,j,n = pp.size(),m,cn,cm,fn,fm,su = 0,fii,cou
      |                                      ^~
books.cpp:37:41: warning: unused variable 'fm' [-Wunused-variable]
   37 |  long long i,j,n = pp.size(),m,cn,cm,fn,fm,su = 0,fii,cou
      |                                         ^~
books.cpp:37:51: warning: unused variable 'fii' [-Wunused-variable]
   37 |  long long i,j,n = pp.size(),m,cn,cm,fn,fm,su = 0,fii,cou
      |                                                   ^~~
books.cpp:38:3: warning: unused variable 'ble' [-Wunused-variable]
   38 |  ,ble = sta,bri = sta,cmi,cva,cri,cle,cl,cr;
      |   ^~~
books.cpp:38:13: warning: unused variable 'bri' [-Wunused-variable]
   38 |  ,ble = sta,bri = sta,cmi,cva,cri,cle,cl,cr;
      |             ^~~
books.cpp:38:23: warning: unused variable 'cmi' [-Wunused-variable]
   38 |  ,ble = sta,bri = sta,cmi,cva,cri,cle,cl,cr;
      |                       ^~~
books.cpp:38:31: warning: unused variable 'cri' [-Wunused-variable]
   38 |  ,ble = sta,bri = sta,cmi,cva,cri,cle,cl,cr;
      |                               ^~~
books.cpp:38:35: warning: unused variable 'cle' [-Wunused-variable]
   38 |  ,ble = sta,bri = sta,cmi,cva,cri,cle,cl,cr;
      |                                   ^~~
books.cpp:38:39: warning: unused variable 'cl' [-Wunused-variable]
   38 |  ,ble = sta,bri = sta,cmi,cva,cri,cle,cl,cr;
      |                                       ^~

• Subtask 1: 12 / 12
• Subtask 2: 0 / 10
• Subtask 3: 0 / 28
• Subtask 4: 0 / 20
• Subtask 5: 0 / 30