[Codeforces/코드포스] Codeforces Round #579 (Div. 3) A - Circle of Students

Problem - 1203A - Codeforces

---

Queue 큐를 사용하자

오름차순과 내림차순

---

---

• 제목

Circle of Students

---

• 조건

time limit per test : 2 second

memory limit per test : 256 megabytes

input : standard input

output : standard output

---

• 문제

There are N students standing in a circle in some order. The index of the i-th student is pipi. It is guaranteed that all indices of students are distinct integers from 1 to N (i. e. they form a permutation).

Students want to start a round dance. A clockwise round dance can be started if the student 2 comes right after the student 1 in clockwise order (there are no students between them), the student 3 comes right after the student 2 in clockwise order, and so on, and the student nncomes right after the student N−1 in clockwise order. A counterclockwise round dance is almost the same thing — the only difference is that the student ii should be right after the student i−1 in counterclockwise order (this condition should be met for every ii from 2 to N).

For example, if the indices of students listed in clockwise order are [2,3,4,5,1], then they can start a clockwise round dance. If the students have indices [3,2,1,4] in clockwise order, then they can start a counterclockwise round dance.

Your task is to determine whether it is possible to start a round dance. Note that the students cannot change their positions before starting the dance; they cannot swap or leave the circle, and no other student can enter the circle.

You have to answer q independent queries.

---

• 입력

The first line of the input contains one integer qq (1≤q≤200) — the number of queries. Then q queries follow.

The first line of the query contains one integer nn (1≤N≤200) — the number of students.

The second line of the query contains a permutation of indices p1,p2,…,pn (1≤pi≤N), where pi is the index of the i-th student (in clockwise order). It is guaranteed that all pipi are distinct integers from 1 to N (i. e. they form a permutation).

---

• 출력

For each query, print the answer on it. If a round dance can be started with the given order of students, print "YES". Otherwise print "NO".

---

예제 입력 1	5  4  1 2 3 4  3  1 3 2  5  1 2 3 5 4  1  1  5  3 2 1 5 4
예제 출력 1	YES  YES  NO  YES  YES

---

#include <iostream>
#include <queue>
using namespace std;

void clear(queue<int>& q) {
	queue<int> empty;
	swap(q, empty);
}

int main() {
	queue<int> q;
	bool up, down;
	int test_case, size, num, tmp, min, max;
 
	cin >> test_case;
 
	for (int n = 0; n < test_case; n++) {
		cin >> size;
		up = down = true;
		min = size;
		max = 1;
		clear(q);
		for (int m = 0; m < size; m++) {
			cin >> num;
			if (min > num)
				min = num;
			if (max < num)
				max = num;
			q.push(num);
		}
 
		if (size == 1) {
			cout << "YES" << endl;
			continue;
		}
 
		for (int m = 0; m < size; m++) {
			if (q.front() == max)
				break;
			tmp = q.front();
			q.pop();
			q.push(tmp);
		}
		for (int m = 0; m < size - 1; m++) {
			tmp = q.front();
			q.pop();
			q.push(tmp);
			if (tmp < q.front()) {
				down = false;
				break;
			}
		}
 
		for (int m = 0; m < size; m++) {
			if (q.front() == min)
				break;
			tmp = q.front();
			q.pop();
			q.push(tmp);
		}
		for (int m = 0; m < size - 1; m++) {
			tmp = q.front();
			q.pop();
			q.push(tmp);
			if (tmp > q.front()) {
				up = false;
				break;
			}
		}
 
		if (up == true || down == true)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
 
	return 0;
}