B. Cosmic Tables
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
The Free Meteor Association (FMA) has got a problem: as meteors are moving, the Universal Cosmic Descriptive Humorous Program (UCDHP) needs to add a special module that would analyze this movement.
UCDHP stores some secret information about meteors as ann×mtable with integers in its cells. The order of meteors in the Universe is changing. That’s why the main UCDHP module receives the following queries:
The query to swap two table rows;The query to swap two table columns;The query to obtain a secret number in a particular table cell.
As the main UCDHP module is critical, writing the functional of working with the table has been commissioned to you.
Input
The first line contains three space-separated integersn,mandk(1≤n,m≤1000,1≤k≤500000) — the number of table columns and rows and the number of queries, correspondingly.
Nextnlines containmspace-separated numbers each — the initial state of the table. Each numberpin the table is an integer and satisfies the inequality0≤p≤106.
Nextklines contain queries in the format "sixiyi", wheresiis one of the characters "с", "r" or "g", andxi,yiare two integers.
Ifsi= "c", then the current query is the query to swap columns with indexesxiandyi(1≤x,y≤m,x≠y);Ifsi= "r", then the current query is the query to swap rows with indexesxiandyi(1≤x,y≤n,x≠y);Ifsi= "g", then the current query is the query to obtain the number that located in thexi-th row and in theyi-th column (1≤x≤n,1≤y≤m).
The table rows are considered to be indexed from top to bottom from 1 ton, and the table columns — from left to right from 1 tom.
Output
For each query to obtain a number (si= "g") print the required number. Print the answers to the queries in the order of the queries in the input.
Sample test(s)
input
3 3 51 2 34 5 67 8 9g 3 2r 3 2c 2 3g 2 2g 3 2
output
896
input
2 3 31 2 43 1 5c 2 1r 1 2g 1 3
output
5
Note
Let’s see how the table changes in the second test case.
After the first operation is fulfilled, the table looks like that:
2 1 4
1 3 5
After the second operation is fulfilled, the table looks like that:
1 3 5
2 1 4
So the answer to the third query (the number located in the first row and in the third column) will be 5.
题解:这一题很巧妙,用b[i]表示现在的第i行是原来的第几行,c[i]表示现在的第i列是原来的第几列。然后只要交换b[x],b[y]就可以了,,答案即是a[b[x]][c[y]]。
#include <iostream>#include <cstdio>#include <algorithm>using namespace std;int n,k,i,t,a[100005];int main(){scanf("%d%d",&n,&k);for (int i=1;i<=n;i++) scanf("%d",&a[i]);i=k;while (a[i]==a[i-1] && i>=0) i–;t=i;for (int i=k;i<=n;i++) if (a[i]!=a[k]){cout <<-1<<endl;return 0;}cout <<t-1<<endl;return 0;}
只要有信心,人永远不会挫败