제출 #30945

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
30945		kajebiii	곤돌라 (IOI14_gondola)	C++14	100 / 100	43 ms	5792 KiB

gondola

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

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<double, double> pd;
typedef pair<int, int> pi; 
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll; typedef pair<ll, pi> plp;
typedef tuple<int, int, int> ti; typedef tuple<ll, int, int> tli;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF * 2;

const int MAX_N = 1e5 + 100;
int temp[MAX_N];
int valid(int n, int nr[]) {
    for(int i=0; i<n; i++) temp[i] = nr[i];
    int ix = -1, cnt = 0;
    for(int i=0; i<n; i++) if(nr[i] >= 1 && nr[i] <= n) {
        ix = i;
        break;
    }
    sort(temp, temp+n);
    for(int i=0; i+1<n; i++) if(temp[i] == temp[i+1]) return 0;

    if(ix == -1) return 1;
    
    ix = (ix + n - (nr[ix]-1)) % n;
    for(int i=0; i<n; i++) {
        int v = nr[(ix+i)%n];
        if(v >= 1 && v <= n && v != (i+1)) return 0; 
    }
    return 1;
}

//----------------------


int replacement(int n, int nr[], int res[]) {
    for(int i=0; i<n; i++) temp[i] = nr[i];

    int ix = -1, cnt = 0;
    for(int i=0; i<n; i++) if(nr[i] >= 1 && nr[i] <= n) {
        ix = i;
        break;
    }
    if(ix != -1) {
        ix = (ix + n - (nr[ix]-1)) % n;
        for(int i=0; i<n; i++) nr[i] = temp[(i+ix)%n];
    }
//    for(int i=0; i<n; i++) printf("%d ", nr[i]); puts("");

    int ansL = 0;
    vector<pi> ps;
    for(int i=0; i<n; i++) ps.push_back(pi(nr[i], i));
    sort(ALL(ps));
    for(int i=0; i<n; i++) nr[i] = i+1;

    int now = n;
    for(int i=0; i<n; i++) {
        while(now < ps[i].one) {
            now++;
            res[ansL++] = nr[ps[i].two];
            nr[ps[i].two] = now;
        }
    }
    return ansL;
}

//----------------------
const int MOD = 1e9 + 9;

int myTemp[MAX_N];
int pow(int a, int b) {
    int res = 1, p = a;
    while(b) {
        if(b&1) res = 1ll * res * p % MOD;
        p = 1ll * p * p % MOD;
        b >>= 1;
    }
    return res;
}
int countReplacement(int n, int nr[]) {
    for(int i=0; i<n; i++) myTemp[i] = nr[i];
    if(valid(n, myTemp) == 0) {
        return 0;
    }
    for(int i=0; i<n; i++) temp[i] = nr[i];

    int ix = -1, cnt = 0;
    for(int i=0; i<n; i++) if(nr[i] >= 1 && nr[i] <= n) {
        ix = i;
        break;
    }
    int ans = 1;
    if(ix != -1) {
        ix = (ix + n - (nr[ix]-1)) % n;
        for(int i=0; i<n; i++) nr[i] = temp[(i+ix)%n];
    }else ans = n;
//    for(int i=0; i<n; i++) printf("%d ", nr[i]); puts("");

    vector<pi> ps;
    for(int i=0; i<n; i++) ps.push_back(pi(nr[i], i));
    sort(ALL(ps));

    int unCh = n;
    int now = n;
    for(int i=0; i<n; i++) {
        if(now < ps[i].one) {
            ans = 1ll * ans * pow(unCh, ps[i].one-now-1) % MOD;
            now = ps[i].one;
        }
        unCh--;
    }
    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:23:18: warning: unused variable 'cnt' [-Wunused-variable]
     int ix = -1, cnt = 0;
                  ^
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:47:18: warning: unused variable 'cnt' [-Wunused-variable]
     int ix = -1, cnt = 0;
                  ^
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:95:18: warning: unused variable 'cnt' [-Wunused-variable]
     int ix = -1, cnt = 0;
                  ^

• 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: 15 / 15
• Subtask 9: 15 / 15
• Subtask 10: 10 / 10