Submission #637796

#	Time	Username	Problem	Language	Result	Execution time	Memory
637796		ogibogi2004	Secret Permutation (RMI19_permutation)	C++14	0 / 100	0 ms	208 KiB

permutation

#include "permutationc.h"
#include<bits/stdc++.h>
using namespace std;
mt19937 mt(69);

/*vector<int>p;
int query(vector<int>v)
{
    int ans=0;
    for(int i=1;i<v.size();i++)
    {
        ans+=abs(p[v[i]]-p[v[i-1]]);
    }
    return ans;
}
void answer(vector<int>v)
{
    for(auto xd:v)cout<<xd<<" ";
    cout<<endl;
}*/
int val[256];
int dif1[256];
int dif2[256];
int c[256];
int n;
void fill_with(int *arr,vector<int>v)
{
    for(int i=0;i<v.size();i++)arr[i]=v[i];
    return;
}
void solve(int N)
{
    n=N;
    int arr[n];
    vector<int>v1;
    for(int i=0;i<n;i++)v1.push_back(i);
    vector<int>answers;
    fill_with(arr,v1);
    answers.push_back(query(arr));
    for(int i=1;i<n;i++)
    {
        v1.clear();
        for(int j=i;j<n;j++)v1.push_back(j);
        for(int j=0;j<i;j++)v1.push_back(j);
        fill_with(arr,v1);
        answers.push_back(query(arr));
    }
    int sum=0;
    for(auto xd:answers)sum+=xd;
    sum/=(n-1);
    //cout<<sum<<endl;
    for(int i=0;i<n;i++)
    {
        dif1[i]=sum-answers[i];
    }
    v1.clear();
    answers.clear();
    vector<int>v2;
    for(int i=0;i<n;i+=2)v2.push_back(i);
    for(int i=1;i<n;i+=2)v2.push_back(i);
    for(int i=0;i<v2.size();i++)
    {
        v1.clear();
        for(int j=i;j<v2.size();j++)v1.push_back(v2[j]);
        for(int j=0;j<i;j++)v1.push_back(v2[j]);
        fill_with(arr,v1);
        answers.push_back(query(arr));
    }
    sum=0;
    for(auto xd:answers)sum+=xd;
    sum/=(n-1);
    for(int i=0;i<v2.size();i++)
    {
        dif2[v2[i]]=sum-answers[i];
    }
    vector<int>ans(n,0);
    ans[1]=ans[0]+dif1[1];
    c[1]=1;
    for(int i=2;i<ans.size();i++)
    {
        if(dif2[i]==dif1[i-1]+dif1[i])
        {
            c[i]=c[i-1];
        }
        else c[i]=-c[i-1];
        ans[i]=ans[i-1]+c[i]*dif1[i];
    }
    int minans=0;
    for(int i=0;i<ans.size();i++)minans=min(minans,ans[i]);
    for(int i=0;i<ans.size();i++)
    {
        ans[i]-=minans;
        ans[i]+=1;
    }
    /*cout<<"difs:\n";
    for(int i=0;i<n;i++)
    {
        cout<<dif1[i]<<" ";
    }
    cout<<endl;
    for(int i=0;i<n;i++)
    {
        cout<<dif2[i]<<" ";
    }
    cout<<endl;
    cout<<endl;*/
    fill_with(arr,ans);
    answer(arr);
}



/*int main()
{
    int N;
    cin>>N;
    for(int i=0;i<N;i++)
    {
        int x;
        cin>>x;
        p.push_back(x);
    }
    solve(N);
}*/

Compilation message (stderr)

permutation.cpp: In function 'void fill_with(int*, std::vector<int>)':
permutation.cpp:28:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(int i=0;i<v.size();i++)arr[i]=v[i];
      |                 ~^~~~~~~~~
permutation.cpp: In function 'void solve(int)':
permutation.cpp:61:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for(int i=0;i<v2.size();i++)
      |                 ~^~~~~~~~~~
permutation.cpp:64:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |         for(int j=i;j<v2.size();j++)v1.push_back(v2[j]);
      |                     ~^~~~~~~~~~
permutation.cpp:72:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |     for(int i=0;i<v2.size();i++)
      |                 ~^~~~~~~~~~
permutation.cpp:79:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i=2;i<ans.size();i++)
      |                 ~^~~~~~~~~~~
permutation.cpp:89:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |     for(int i=0;i<ans.size();i++)minans=min(minans,ans[i]);
      |                 ~^~~~~~~~~~~
permutation.cpp:90:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |     for(int i=0;i<ans.size();i++)
      |                 ~^~~~~~~~~~~
stub.cpp: In function 'int query(int*)':
stub.cpp:15:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |   fscanf(stdin, "%d", &x);
      |   ~~~~~~^~~~~~~~~~~~~~~~~
stub.cpp: In function 'int main(int, char**)':
stub.cpp:48:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |   fscanf(stdin, "%d", &N);
      |   ~~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 35
• Subtask 3: 0 / 50