oj.uz

Submission #775809

# Submission time Handle Problem Language Result Execution time Memory
775809 2023-07-07T04:04:57 Z Amylopectin Ancient Books (IOI17_books) C++14
12 / 100
 1 ms 340 KB 
#include "books.h"
#include <vector>
#include <algorithm>
using namespace std;
const long long mxn = 4e6 + 10;
struct we
{
	long long le,ri;
};
bool cmp(const struct we &l,const struct we &r)
{
	return l.ri > r.ri;
}
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;
	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;
			while(1)
			{
				if(cn <= sta)
				{
					cyc[ru].le = fima(cyc[ru].le,cn);
				}
				else 
				{
					cyc[ru].ri = fimi(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 ++;
			}
		}
	}
	sort(cyc,cyc+ru,cmp);
	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 + cmi * 2;
}

Compilation message

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

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 300 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 292 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 292 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 300 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 292 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 292 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Incorrect 1 ms 340 KB 3rd lines differ - on the 1st token, expected: '2082', found: '2782'
23 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 300 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 292 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 292 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Incorrect 1 ms 340 KB 3rd lines differ - on the 1st token, expected: '2082', found: '2782'
23 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 292 KB 3rd lines differ - on the 1st token, expected: '3304', found: '4724'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 296 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 0 ms 300 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 292 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 292 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 1 ms 212 KB Output is correct
22 Incorrect 1 ms 340 KB 3rd lines differ - on the 1st token, expected: '2082', found: '2782'
23 Halted 0 ms 0 KB -