Submission #285840

#	Time	Username	Problem	Language	Result	Execution time	Memory
285840		stefanbalaz2	Shift (POI11_prz)	C++14	100 / 100	328 ms	40764 KiB

prz

/*

    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 (stderr)

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]);
      |         ~~~~~^~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 13 / 13
• Subtask 8: 13 / 13