「CF400C」Inna and Huge Candy Matrix
Inna and Dima decided to surprise Sereja. They brought a really huge candy matrix, it’s big even for Sereja! Let’s number the rows of the giant matrix from 1 to n from top to bottom and the columns — from 1 to m, from left to right. We’ll represent the cell on the intersection of the i-th row and j-th column as (i, j). Just as is expected, some cells of the giant candy matrix contain candies. Overall the matrix has p candies: the k-th candy is at cell (xk, yk).
The time moved closer to dinner and Inna was already going to eat p of her favourite sweets from the matrix, when suddenly Sereja (for the reason he didn’t share with anyone) rotated the matrix x times clockwise by 90 degrees. Then he performed the horizontal rotate of the matrix y times. And then he rotated the matrix z times counterclockwise by 90 degrees. The figure below shows how the rotates of the matrix looks like.
The first line of the input contains fix integers n, m, x, y, z, p (1 ≤ n, m ≤ 109; 0 ≤ x, y, z ≤ 109; 1 ≤ p ≤ 105).
Each of the following p lines contains two integers xk, yk (1 ≤ xk ≤ n; 1 ≤ yk ≤ m) — the initial coordinates of the k-th candy. Two candies can lie on the same cell.
For each of the p candies, print on a single line its space-separated new coordinates.
|
1 2 3 4 5 6 7 8 9 10 |
3 3 3 1 1 9 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3 |
|
1 2 3 4 5 6 7 8 9 |
1 3 1 2 1 1 2 3 2 2 2 1 3 3 3 2 3 1 |
Just for clarity. Horizontal rotating is like a mirroring of the matrix. For matrix:
|
1 2 3 |
QWER REWQ ASDF -> FDSA ZXCV VCXZ |
看了眼数据范围。非常激动地写了个矩阵乘法。其实把xyz取模就。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; int n,m,a1,a2,a3,p; int b[5][5],r[5][5],l[5][5],f[5][5]; void mul(int a[5][5],int b[5][5],int ans[5][5]) { int t[5][5]; for(int i=1;i<5;i++) for(int j=1;j<5;j++) { t[i][j]=0; for(int k=1;k<5;k++) t[i][j]+=a[i][k]*b[k][j]; } for(int i=1;i<5;i++) for(int j=1;j<5;j++) ans[i][j]=t[i][j]; } void mul2(int a[5],int b[5][5],int ans[5]) { int t[5]; for(int j=1;j<5;j++) { t[j]=0; for(int k=1;k<5;k++) t[j]+=a[k]*b[k][j]; } for(int j=1;j<5;j++) ans[j]=t[j]; } int main() { scanf("%d%d%d%d%d%d",&n,&m,&a1,&a2,&a3,&p); b[1][1]=b[2][2]=b[3][3]=b[4][4]=1; r[2][1]=1;r[3][2]=1;r[1][2]=-1;r[4][3]=1;r[3][4]=1; f[1][1]=1;f[4][2]=1;f[2][2]=-1;f[3][3]=1;f[4][4]=1; l[2][1]=-1;l[4][1]=1;l[1][2]=1;l[4][3]=1;l[3][4]=1; while(a1) { if(a1&1)mul(b,r,b); a1>>=1; mul(r,r,r); } while(a2) { if(a2&1)mul(b,f,b); a2>>=1; mul(f,f,f); } while(a3) { if(a3&1)mul(b,l,b); a3>>=1; mul(l,l,l); } int a[5]; for(int i=1;i<=p;i++) { scanf("%d%d",&a[1],&a[2]); a[3]=n+1;a[4]=m+1; mul2(a,b,a); printf("%d %d\n",a[1],a[2]); } return 0; } |
OI 课件=>
