Submission #853048

#	Time	Username	Problem	Language	Result	Execution time	Memory
853048		aykhn	Gondola (IOI14_gondola)	C++14	60 / 100	25 ms	5844 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

#define pb push_back
#define ins insert
#define infll 0x3F3F3F3F3F3F3F3F
#define inf 0x3F3F3F3F
#define pii pair<int, int>
#define pll pair<ll, ll>
#define mpr make_pair
#define all(v) v.begin(), v.end()
#define fi first
#define se second

const int mod = 1e9 + 7;

int mult(ll a, ll b)
{
    return (a * b) % mod;
}

int binpow(ll a, ll b)
{
    a %= mod;
    ll res = 1;
    while (b)
    {
        if (b & 1) res = mult(res, a);
        b >>= 1;
        a = mult(a, a);
    }
    return res;
}

vector<int> ASDASD;

int ok(vector<int> &v)
{
    int n = v.size();
    set<int> s;
    for (int x : v) s.ins(x);
    if (s.size() != v.size()) return 0;
    vector<int> a(n, 0);
    int anc = -1;
    for (int i = 0; i < v.size(); i++)
    {
        if (v[i] <= n) 
        {
            anc = i;
            break;
        }
    }
    if (anc == -1) 
    {
        ASDASD = v;
        return 1;
    }
    int shift = n + v[anc] - anc - 1;
    for (int i = 0; i < n; i++) a[(i + shift + 10*n) % n] = v[i];
    ASDASD = a;
    for (int i = 0; i < n; i++)
    {
        if (a[i] <= n && a[i] != i + 1) return 0;
    }
    return 1;
}

int valid(int n, int in[])
{
    vector<int> v;
    for (int i = 0; i < n; i++) v.pb(in[i]);
    return ok(v);
}

int replacement(int n, int in[], int ret[])
{
    vector<int> v;
    for (int i = 0; i < n; i++) v.pb(in[i]);
    ok(v);
    v = ASDASD;
    vector<pii> a;
    for (int i = 0; i < v.size(); i++)
    {
        if (v[i] == i + 1) continue;
        a.pb(mpr(v[i], i + 1));
    }
    sort(all(a));
    int j = 0;
    int rn = n + 1;
    for (int i = 0; i < a.size(); i++)
    {
        ret[j++] = a[i].se;
        while (a[i].fi > rn) ret[j++] = rn++;
        rn++;
    }
    return j;
}

int countReplacement(int n, int in[])
{
    vector<int> v;
    for (int i = 0; i < n; i++) v.pb(in[i]);
    if (!ok(v)) return 0;
    v = ASDASD;
    vector<pii> a;
    for (int i = 0; i < v.size(); i++)
    {
        if (v[i] == i + 1) continue;
        a.pb(mpr(v[i], i + 1));
    }
    int x = 1;
    if (a.size() == v.size()) x = n;
    sort(all(a));
    int last = n;
    int res = 1;
    int sz = a.size();
    for (int i = 0; i < a.size(); i++) 
    {
        res = mult(res, binpow(sz - i, a[i].fi - last - 1));
        last = a[i].fi;
    }
    return mult(res, x);
}

Compilation message (stderr)

gondola.cpp: In function 'int ok(std::vector<int>&)':
gondola.cpp:48:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:85:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~
gondola.cpp:93:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for (int i = 0; i < a.size(); i++)
      |                     ~~^~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:109:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  109 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~
gondola.cpp:120:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |     for (int i = 0; i < a.size(); i++)
      |                     ~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 5 / 5
• Subtask 8: 0 / 15
• Subtask 9: 0 / 15
• Subtask 10: 0 / 10