Submission 122303 | MatCom Online Grader

Id	Date	User	Problem	Result	Time	Mem	Lang
122303	01/03/2018 21:54:39	leandro	C - Permutando secuencias	Accepted	625	1.2 MiB	GNU G++11 5.1.0

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;
typedef pair<ll, pii> piii;

#define SZ(c) ((int)(c).size())

#define D first
#define X second.first
#define Y second.second

piii ext_gcd(ll a, ll b) {
    if (!b)
        return {a, {1, 0}};
        
    piii q = ext_gcd(b, a % b);
    return {q.D, {q.Y, q.X - a / b * q.Y}};
}

ll mod_mul(ll a, ll b, ll mod) {
    ll r = 0;
    while (b) {
        if (b & 1)
            r = (r + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return r;
}

ll signed_mod_mul(ll a, ll b, ll mod) {
    int sa = a > 0 ? +1 : -1;
    int sb = b > 0 ? +1 : -1;
    ll p = mod_mul(abs(a), abs(b), mod);
    return (p * sa * sb + mod) % mod;
}

#define MUL(x, y, m) signed_mod_mul(x, y, m)

bool chinese_remainder_theorem(ll a1, ll b1, ll & a2, ll & b2) {
    ll g = __gcd(b1, b2);
    if ((a1 - a2) % g != 0)
        return false;
    
    ll l = b1 / g * b2;
    piii t = ext_gcd(b1, b2);
    ll f = (a1 - a2) / g;
    ll w = MUL(MUL(-t.X, b1, l), f, l) + a1;
    a2 = (w + l) % l;
    b2 = l;
    return true;
}

#define VAL first
#define POS second

const int MAXN = 300;
const int MAXM = 100100;

int n, m, p[MAXN], x[MAXM], c, cidx[MAXN], idx[MAXN];
vector<pii> cycles[MAXN];
int sol[MAXM];
bool mk[MAXN];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> p[i];
        p[i]--;
    }
    
    cin >> m;
    for (int i = 0; i < m; i++) {
        cin >> x[i];
        x[i]--;
    }
    
    for (int i = 0; i < n; i++) {
        if (!mk[i]) {
            int j = i;
            int k = 0;
            while (!mk[j]) {
                mk[j] = true;
                cycles[c].push_back({j, k});
                idx[j] = k;
                cidx[j] = c;
                k++;
                j = p[j];
            }
            sort(cycles[c].begin(), cycles[c].end());
            c++;
        }
    }
    
    
    ll a1 = 0;
    ll m1 = 1;
    
    for (int i = 0; i < m; i++) {
        int ci = cidx[x[i]];
        int k = SZ(cycles[ci]);
        for (auto vp : cycles[ci]) {
            ll a2 = (vp.POS - idx[x[i]] + k) % k;
            ll m2 = k;
            
            //~ cerr << a2 << "_" << m2 << endl;
            
            if (chinese_remainder_theorem(a1, m1, a2, m2)) {
                sol[i] = vp.VAL;
                a1 = a2;
                m1 = m2;
                break;
            }
        }
        //~ cerr << a1 << " " << m1 << endl;
    }
    
    cout << a1 << endl;
    for (int i = 0; i < m; i++)
        cout << sol[i]+1 << " \n "[i==n-1];
}

Judgement Details

Case#1 [1232896 bytes][264 ms]: ok 48438 tokens
Case#2 [1228800 bytes][62 ms]: ok 8329 tokens
Case#3 [1228800 bytes][46 ms]: ok 24361 tokens
Case#4 [1232896 bytes][153 ms]: ok 77283 tokens
Case#5 [1228800 bytes][47 ms]: ok 7227 tokens
Case#6 [1228800 bytes][93 ms]: ok 62216 tokens
Case#7 [1228800 bytes][140 ms]: ok 64968 tokens
Case#8 [1228800 bytes][280 ms]: ok 70377 tokens
Case#9 [1228800 bytes][106 ms]: ok 36702 tokens
Case#10 [1232896 bytes][17 ms]: ok 1560 tokens
Case#11 [1228800 bytes][287 ms]: ok 94378 tokens
Case#12 [1232896 bytes][344 ms]: ok 76296 tokens
Case#13 [1232896 bytes][158 ms]: ok 83492 tokens
Case#14 [1232896 bytes][30 ms]: ok 42110 tokens
Case#15 [1228800 bytes][109 ms]: ok 45661 tokens
Case#16 [1228800 bytes][109 ms]: ok 33557 tokens
Case#17 [1241088 bytes][78 ms]: ok 16921 tokens
Case#18 [1228800 bytes][30 ms]: ok 1697 tokens
Case#19 [1232896 bytes][140 ms]: ok 54443 tokens
Case#20 [1228800 bytes][239 ms]: ok 99892 tokens
Case#21 [1232896 bytes][312 ms]: ok 80039 tokens
Case#22 [1241088 bytes][299 ms]: ok 67262 tokens
Case#23 [1232896 bytes][75 ms]: ok 20603 tokens
Case#24 [1228800 bytes][78 ms]: ok 38380 tokens
Case#25 [1232896 bytes][234 ms]: ok 94390 tokens
Case#26 [1228800 bytes][428 ms]: ok 97919 tokens
Case#27 [1228800 bytes][214 ms]: ok 74858 tokens
Case#28 [1228800 bytes][110 ms]: ok 30609 tokens
Case#29 [1228800 bytes][140 ms]: ok 39422 tokens
Case#30 [1232896 bytes][79 ms]: ok 18688 tokens
Case#31 [1236992 bytes][187 ms]: ok 42240 tokens
Case#32 [1228800 bytes][151 ms]: ok 85494 tokens
Case#33 [1228800 bytes][168 ms]: ok 32624 tokens
Case#34 [1228800 bytes][15 ms]: ok 3519 tokens
Case#35 [1228800 bytes][46 ms]: ok 12973 tokens
Case#36 [1232896 bytes][75 ms]: ok 34098 tokens
Case#37 [1232896 bytes][234 ms]: ok 96594 tokens
Case#38 [1228800 bytes][203 ms]: ok 97687 tokens
Case#39 [1232896 bytes][187 ms]: ok 80604 tokens
Case#40 [1236992 bytes][469 ms]: ok 88358 tokens
Case#41 [1232896 bytes][280 ms]: ok 83179 tokens
Case#42 [1228800 bytes][108 ms]: ok 37595 tokens
Case#43 [1228800 bytes][62 ms]: ok 41879 tokens
Case#44 [1236992 bytes][328 ms]: ok 62977 tokens
Case#45 [1232896 bytes][281 ms]: ok 77600 tokens
Case#46 [1232896 bytes][93 ms]: ok 48731 tokens
Case#47 [1232896 bytes][31 ms]: ok 3495 tokens
Case#48 [1228800 bytes][232 ms]: ok 87439 tokens
Case#49 [1236992 bytes][375 ms]: ok 77516 tokens
Case#50 [1228800 bytes][77 ms]: ok 32056 tokens
Case#51 [1236992 bytes][325 ms]: ok 77721 tokens
Case#52 [1228800 bytes][109 ms]: ok 29402 tokens
Case#53 [1228800 bytes][265 ms]: ok 83451 tokens
Case#54 [1232896 bytes][91 ms]: ok 99750 tokens
Case#55 [1236992 bytes][120 ms]: ok 31224 tokens
Case#56 [1232896 bytes][62 ms]: ok 32181 tokens
Case#57 [1228800 bytes][205 ms]: ok 89081 tokens
Case#58 [1241088 bytes][201 ms]: ok 44951 tokens
Case#59 [1228800 bytes][124 ms]: ok 46778 tokens
Case#60 [1236992 bytes][532 ms]: ok 100001 tokens
Case#61 [1236992 bytes][515 ms]: ok 100001 tokens
Case#62 [1236992 bytes][499 ms]: ok 100001 tokens
Case#63 [1236992 bytes][466 ms]: ok 100001 tokens
Case#64 [1241088 bytes][610 ms]: ok 100001 tokens
Case#65 [1241088 bytes][452 ms]: ok 100001 tokens
Case#66 [1236992 bytes][447 ms]: ok 100001 tokens
Case#67 [1228800 bytes][342 ms]: ok 100001 tokens
Case#68 [1236992 bytes][420 ms]: ok 100001 tokens
Case#69 [1241088 bytes][546 ms]: ok 100001 tokens
Case#70 [1241088 bytes][625 ms]: ok 100001 tokens

Matcom Online Grader