oj.uz

Submission #649865

# Submission time Handle Problem Language Result Execution time Memory
649865 2022-10-11T13:23:50 Z boris_mihov Secret Permutation (RMI19_permutation) C++17
0 / 100
 1 ms 208 KB 
#include "permutation.h"
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <cassert>
#include <vector>
#include <cmath>
#include <set>

const int MAXN = 256 + 10;
const int INF  = 1e9;

// int p[MAXN];
// int query(std::vector <int> v)
// {
//     int sum = 0;
//     for (int i = 0 ; i < v.size() - 1 ; ++i)
//     {
//         sum += abs(p[v[i + 1]] - p[v[i]]);
//     }

//     return sum;
// }

// int N;
// void answer(std::vector <int> v)
// {
//     int cnt = 1;
//     bool res = true;
//     for (const int &i : v)
//     {
//         std::cout << i << ' ';
//         res &= (i == p[cnt++]);
//     }
    
//     if (!res)
//     {
//         cnt = 1;
//         res = true;
//         for (const int &i : v)
//         {
//             res &= (i == N+1 - p[cnt++]);
//         }
//     }

//     std::cout << '\n';
//     if (res) std::cout << "OK\n";
//     else std::cout << "WA\n";
//     exit(0);
//     // if (!res)
//     // {
//     //     for (int i = 1 ; i <= N ; ++i)
//     //     {
//     //         std::cout << p[i] << ' ';
//     //     }

//     //     std::cout << '\n';
//     //     exit(0);
//     // }
// }

// inline void printVector(const std::vector <int> &v)
// {
//     for (const int &i : v)
//     {
//         std::cout << i << ' ';
//     }

//     std::cout << '\n';
// }

std::vector <int> perm;
std::vector <int> ans;
void solve(int n) 
{
    perm.resize(n);
    std::iota(perm.begin(), perm.end(), 1);
    for (int i = 2 ; i <= n-1 ; ++i)
    {
        perm.erase(perm.begin() + i);
        int minPos = -1, value = INF;
        for (int j = 0 ; j <= i ; ++j)
        {
            perm.insert(perm.begin() + j, i+1);
            // printVector(perm);
            int curr = query(perm);
            if (curr <= value)
            {
                minPos = j;
                value = curr; 
            }

            perm.erase(perm.begin() + j);
        }

        perm.insert(perm.begin() + minPos, i+1);
    }

    ans.resize(n);
    for (int i = 1 ; i <= n ; ++i)
    {
        ans[perm[i-1] - 1] = i;
    }

    answer(ans);
}

// int n;
// int main()
// {
//     std::cin >> n;
//     for (int i = 1 ; i <= n ; ++i)
//     {
//         std::cin >> p[i];
//     }

//     solve(n);
//     // n = 5;
//     // N = n;
//     // std::iota(p + 1, p + 1 + n, 1);
//     // do
//     // {
//     //     solve(n);
//     //     std::random_shuffle(p + 1, p + 1 + n);
//     // } while(true);
//     // return 0;
// }

Compilation message

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.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 35.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 208 KB Output isn't correct
2 Halted 0 ms 0 KB -