oj.uz

Submission #58563

# Submission time Handle Problem Language Result Execution time Memory
58563 2018-07-18T08:05:29 Z YaDon4ick Xylophone (JOI18_xylophone) C++14
0 / 100
 3 ms 504 KB 
//By Don4ick
//#define _GLIBCXX_DEBUG

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


typedef long long ll;
typedef long double ld;
typedef unsigned int ui;

#define forn(i, n) for (int i = 1; i <= n; i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define y1 qwer1234

const double PI = acos(-1.0);
const int DIR = 4;
const int X[] = {1, 0, -1, 0};
const int Y[] = {0, 1, 0, -1};

using namespace std;


void solve(int n) {	
	int pos = -1;
	//~binary_search
	{
		int l = 0, r = n + 1;
		while(l < r - 1)
		{
			int mid = (l + r) >> 1;
			if (query(mid, n) == n - 1)
				l = mid;
			else
				r = mid;			
		}
		pos = l;
	}
	answer(pos, 1);
	//~solve(1, pos)
	if (pos > 1)
	{	
		int y = n, x = query(pos - 1, pos) + 1;
		answer(pos - 1, x);
		for (int i = pos - 2; i >= 1; i--)
		{
			int value = query(i, i + 2);
			if (value > abs(x - y))
			{
				int newValue = query(i, i + 1);
				if (x < y)
				{
					if (newValue == value)
					{
						y = x + value;
						swap(x, y);
						answer(i, x);
					}
					else
					{
						y = x - newValue;
						swap(x, y);
						answer(i, x);
					}
				}				
				else
				{
					if (newValue == value)
					{
						y = x - value;
						swap(x, y);
						answer(i, x);
					}
					else
					{
						y = x + newValue;
						swap(x, y);
						answer(i, x);
					}
				}
			}
			else
			{
				int newValue = query(i, i + 1);			
				if (x < y)
				{
					y = x + newValue;
					swap(x, y);
					answer(i, x);	
				}
				else
				{
					y = x - newValue;
					swap(x, y);
					answer(i, x);
				}
			}
		} 
	}
	//~solve(pos, n)
	if (pos < n)
	{
		int y = 1, x = query(pos, pos + 1) + 1;
		answer(pos + 1, x);		
		for (int i = pos + 2; i <= n; i++)
		{
			int value = query(i - 2, i);
			if (value > abs(x - y))
			{
				int newValue = query(i - 1, i);
				if (x < y)
				{
					if (newValue == value)
					{
						y = x + value;
						swap(x, y);
						answer(i, x);
					}
					else
					{
						y = x - newValue;
						swap(x, y);
						answer(i, x);
					}
				}				
				else
				{
					if (newValue == value)
					{
						y = x - value;
						swap(x, y);
						answer(i, x);
					}
					else
					{
						y = x + newValue;
						swap(x, y);
						answer(i, x);
					}
				}
			}
			else
			{
				int newValue = query(i - 1, i);			
				if (x < y)
				{
					y = x + newValue;
					swap(x, y);
					answer(i, x);	
				}
				else
				{
					y = x - newValue;
					swap(x, y);
					answer(i, x);
				}
			}
		}
	}
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Incorrect 2 ms 504 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Incorrect 2 ms 504 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 3 ms 504 KB Output is correct
3 Incorrect 2 ms 504 KB Wrong Answer [7]
4 Halted 0 ms 0 KB -