CodeForces 668B Little Artem and Dance
3670 단어 codeforces668B
time limit per test
2 second
memory limit per test
256 megabytes
input
standard input
output
standard output
Little Artem is fond of dancing. Most of all dances Artem likes rueda — Cuban dance that is danced by pairs of boys and girls forming a circle and dancing together.
More detailed, there are n pairs of boys and girls standing in a circle. Initially, boy number 1 dances with a girl number 1, boy number 2dances with a girl number 2 and so on. Girls are numbered in the clockwise order. During the dance different moves are announced and all pairs perform this moves. While performing moves boys move along the circle, while girls always stay at their initial position. For the purpose of this problem we consider two different types of moves:
Value x and some direction are announced, and all boys move x positions in the corresponding direction.
Boys dancing with even-indexed girls swap positions with boys who are dancing with odd-indexed girls. That is the one who was dancing with the girl 1 swaps with the one who was dancing with the girl number 2, while the one who was dancing with girl number 3swaps with the one who was dancing with the girl number 4 and so one. It's guaranteed that n is even.
Your task is to determine the final position of each boy.
Input
The first line of the input contains two integers n and q (2 ≤ n ≤ 1 000 000, 1 ≤ q ≤ 2 000 000) — the number of couples in the rueda and the number of commands to perform, respectively. It's guaranteed that n is even.
Next q lines contain the descriptions of the commands. Each command has type as the integer 1 or 2 first. Command of the first type is given as x ( - n ≤ x ≤ n), where 0 ≤ x ≤ n means all boys moves x girls in clockwise direction, while - x means all boys move x positions in counter-clockwise direction. There is no other input for commands of the second type.
Output
Output n integers, the i-th of them should be equal to the index of boy the i-th girl is dancing with after performing all q moves.
Examples
input
6 3
1 2
2
1 2
output
4 3 6 5 2 1
input
2 3
1 1
2
1 -2
output
1 2
input
4 2
2
1 3
output
1 4 3 2
일단 1, 2의 위치를 정했고,
다른 숫자의 위치 변동은 1, 2와 똑같을 거예요.
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>
using namespace std;
#define MAX 1000000
int n,q;
int c[MAX+5];
int x,y;
int main()
{
scanf("%d%d",&n,&q);
int a=1;int b=2;
for(int i=1;i<=q;i++)
{
scanf("%d",&x);
if(x==1)
{
scanf("%d",&y);
a=(a+y+n)%n;
if(a==0)
a=n;
b=(b+y+n)%n;
if(b==0)
b=n;
}
else
{
if(a&1) a+=1;
else a-=1;
if(b&1) b+=1;
else b-=1;
}
}
a-=1;
b-=2;
for(int i=1;i<=n;i++)
{
if(i&1)
{
int pos=(i+a)%n;
if(pos==0)
pos=n;
c[pos]=i;
}
else
{
int pos=(i+b)%n;
if(pos==0)
pos=n;
c[pos]=i;
}
}
for(int i=1;i<=n;i++)
{
if(i==n)
printf("%d
",c[i]);
else
printf("%d ",c[i]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Codeforces Round #715 Div. 2C The Sports Festival: 구간 DP전형구간 DP의 초전형. 이하, 0-indexed. 입력을 정렬하여 어디서나 시작하고 최적으로 좌우로 계속 유지하면 좋다는 것을 알 수 있습니다. {2000})$의 주문이 된다. 우선, 입력을 소트하여 n개의 요소를 $...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.