| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 285840 |
2020-08-29T16:22:29 Z |
stefanbalaz2 |
Shift (POI11_prz) |
C++14 |
|
328 ms |
40764 KB |
/*
idea:
*/
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define ff first
#define ss second
#define ll long long
typedef pair<int,int> pii;
typedef pair<int,char> pic;
const int maxn=2010;
vector<pic>rez;
int n,cp,a[maxn],pos[maxn];
void rotation3(int x){
///printf("%d ROTATE\n",x);
int id[3]={x%n,(x+1)%n,(x+2)%n};
int pom=a[id[0]];
int p0=a[id[0]];
int p1=a[id[1]];
int p2=a[id[2]];
a[id[0]]=p2;
pos[p2]=id[0];
a[id[2]]=p1;
pos[p1]=id[2];
a[id[1]]=p0;
pos[p0]=id[1];
}
int dist(int x,int y){
swap(x,y);
if(x<y)return y-x;
else return n-x+y;
}
void rot3(int x,int val){
if(cp!=x){
rez.pb({dist(cp,x),'a'});
cp=x;
}
rez.pb({val,'b'});
for(int i=1;i<=val;i++)rotation3(x);
}
int inversions(){
int ret=0;
for(int i=0;i<n-1;i++)
for(int j=i+1;j<n;j++)
if(a[i]>a[j])ret++;
return ret;
}
bool isNO(){
if(n%2==0)return false;
if(inversions()%2==1)return true;
return false;
}
int find_num(int x){
return pos[x];
}
void ispis(){
for(int i=0;i<n;i++)printf("%d ",a[i]);
printf(" >>\n\n");
}
void go(){
for(int i=2;i<=n;i++){
///printf("%d III\n",i);
///ispis();
if(find_num(i)==(find_num(i-1)+1)%n)continue;
///printf("%d III\n",i);
///ispis();
if(i<=n-2){
while((pos[i-1]+1)%n!=pos[i] && (pos[i-1]+2)%n!=pos[i])
rot3((pos[i]-2+n)%n,1);
if((pos[i-1]+1)%n==pos[i])continue;
else rot3((pos[i]-1+n)%n,2);
}
else{
if(n%2==0){
while((pos[i-1]+1)%n!=pos[i]){
///printf("%d %d AAA\n",(pos[i-1]+1)%n,pos[i]);
///ispis();
rot3((pos[i]-2+n)%n,1);
}
}
else return;
}
///printf("%d III\n",i);
///ispis();
}
}
int main(){
///freopen("test.txt","r",stdin);
///freopen("out.txt","w",stdout);
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d",&a[i]);
pos[a[i]]=i;
}
if(n==1){
printf("%d\n",0);
return 0;
}
if(n==2){
if(a[0]==1)printf("%d\n",0);
else printf("1\n1a\n");
return 0;
}
if(isNO()){
printf("NIE DA SIE\n");
return 0;
}
go();
if(cp!=pos[1])rez.pb({dist(cp,pos[1]),'a'});
vector<pic>rez2;
if(rez.size()>0)rez2.pb(rez[0]);
for(int i=1;i<rez.size();i++)
if(rez[i].ss==rez2.back().ss)rez2[rez2.size()-1].ff+=rez[i].ff;
else rez2.pb(rez[i]);
printf("%d\n",rez2.size());
for(int i=0;i<rez2.size();i++){
printf("%d%c ",rez2[i].ff,rez2[i].ss);
}
printf("\n");
return 0;
}
Compilation message
prz.cpp: In function 'void rotation3(int)':
prz.cpp:23:9: warning: unused variable 'pom' [-Wunused-variable]
23 | int pom=a[id[0]];
| ^~~
prz.cpp: In function 'int main()':
prz.cpp:145:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
145 | for(int i=1;i<rez.size();i++)
| ~^~~~~~~~~~~
prz.cpp:149:14: warning: format '%d' expects argument of type 'int', but argument 2 has type 'std::vector<std::pair<int, char> >::size_type' {aka 'long unsigned int'} [-Wformat=]
149 | printf("%d\n",rez2.size());
| ~^ ~~~~~~~~~~~
| | |
| int std::vector<std::pair<int, char> >::size_type {aka long unsigned int}
| %ld
prz.cpp:150:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, char> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
150 | for(int i=0;i<rez2.size();i++){
| ~^~~~~~~~~~~~
prz.cpp:118:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
118 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
prz.cpp:120:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
120 | scanf("%d",&a[i]);
| ~~~~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Correct |
0 ms |
256 KB |
Output is correct |
| 6 |
Correct |
0 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
384 KB |
Output is correct |
| 2 |
Correct |
0 ms |
256 KB |
Output is correct |
| 3 |
Correct |
1 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
384 KB |
Output is correct |
| 2 |
Correct |
1 ms |
256 KB |
Output is correct |
| 3 |
Correct |
1 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
640 KB |
Output is correct |
| 2 |
Correct |
3 ms |
640 KB |
Output is correct |
| 3 |
Correct |
2 ms |
640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
1656 KB |
Output is correct |
| 2 |
Correct |
11 ms |
1656 KB |
Output is correct |
| 3 |
Correct |
10 ms |
1528 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
110 ms |
17628 KB |
Output is correct |
| 2 |
Correct |
114 ms |
17628 KB |
Output is correct |
| 3 |
Correct |
118 ms |
17624 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
138 ms |
18908 KB |
Output is correct |
| 2 |
Correct |
142 ms |
19036 KB |
Output is correct |
| 3 |
Correct |
140 ms |
19200 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
172 ms |
20456 KB |
Output is correct |
| 2 |
Correct |
172 ms |
20568 KB |
Output is correct |
| 3 |
Correct |
328 ms |
40764 KB |
Output is correct |
| 4 |
Correct |
3 ms |
384 KB |
Output is correct |
| 5 |
Correct |
3 ms |
384 KB |
Output is correct |
