Submission #2741871

Source Code Expand

Copy
#include <bits/stdc++.h>
using namespace std;

#define NDEBUG
#ifdef DEBUG
#include "../cout11.h"
#undef NDEBUG
#endif
#include <cassert>

typedef long long ll;
typedef long double Double;
typedef unsigned long long ull;
typedef pair<int,int> ii;
typedef pair<ll,ll> llll;
typedef pair<double,double> dd;

typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<ll> vll;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<long double> vD;

#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);++var)
#define rep(var,n)  for(int var=0;var<(n);++var)
#define rep1(var,n)  for(int var=1;var<=(n);++var)
#define repC2(vari,varj,n)  for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj)
#define ALL(c)  (c).begin(),(c).end()
#define RALL(c)  (c).rbegin(),(c).rend()
#define tr(i,c)  for(auto i=(c).begin(); i!=(c).end(); ++i)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define mid(x,y) ((x)+((y)-(x))/2)
#define IN(x,a,b) ((a)<=(x)&&(x)<=(b))
#define cons make_pair


#define ABYSS -1
#define TO_BE_FILLED 0

vi solve(int N, int A, int B) {
    vi ans;
    if (A+B > N+1) return ans;
    if (A*B < N) return ans;
    if (A < B) {
        vi rev = solve(N, B, A);
        rep(i,N) rev[i] = (N+1)-rev[i];
        return rev;
    }
    // A >= B
    // A+B <= N+1
    // A*B >= N
    ans.assign(N, -1);
    if (B == 1) {
        rep(i,N) ans[i] = 1+i;
        return ans;
    }

    int rest = N-A, q = rest/(B-1), r = rest%(B-1), _r = (B-1)-r;
    int label=0;
    // for (int i=0;i<A;++i) {
#ifdef DEBUG
    fprintf(stderr, "N=%d,A=%d,B=%d; q=%d,r=%d|%d\n", N,A,B,q,r,_r);
#endif
    for (int i=0; ; ++i) {
        for (int b=min(i,B-1);b>=0;--b) {
            int a = i-b;
            if (A-1 < a) continue;
            if (q+1 <= a) b=0; // jump
            int _b = (B-1)-b; //0...B-1

            int fill_index = -1;
            if (_b < _r) {
                if (q <= a) continue;
                fill_index = _b*q + a;
            } else if (r != 0 && _b < B-1) {
                if (q+1 <= a) continue;
                fill_index = _r*q + (_b-_r)*(q+1) + a;
            } else {
                fill_index = rest + a;
            }
#ifdef DEBUG
            fprintf(stderr, "(%d,%d|%d) -> %d\n", a,b,_b, fill_index);
#endif
            if (fill_index >= 0) {
                ans[fill_index] = ++label;
                if (label == N) goto done;
            }
        }
    }
 done:
    return ans;
}

int main() {
    int N,A,B; cin >> N >> A>> B;
    vi ans = solve(N,A,B);
    if (ans.size() != N) {
        cout << -1 << endl;
    } else {
        rep(i,N) {
            if (i != 0) cout << " ";
            cout << ans[i];
        }
        cout << endl;
    }
    return 0;
}

Submission Info

Submission Time
Task E - LISDL
User naoya_t
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3009 Byte
Status
Exec Time 30 ms
Memory 3456 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 s1.txt, s2.txt, s3.txt
All 0 / 700 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, s1.txt, s2.txt, s3.txt
Case Name Status Exec Time Memory
01.txt 10 ms 1152 KB
02.txt 2 ms 384 KB
03.txt 15 ms 1664 KB
04.txt 2 ms 256 KB
05.txt 26 ms 2944 KB
06.txt 1 ms 256 KB
07.txt 1 ms 256 KB
08.txt 13 ms 1536 KB
09.txt 16 ms 1920 KB
10.txt 26 ms 2688 KB
11.txt 1 ms 256 KB
12.txt 30 ms 3456 KB
13.txt 1 ms 256 KB
14.txt 22 ms 2432 KB
15.txt 8 ms 896 KB
16.txt 27 ms 2944 KB
17.txt 2 ms 256 KB
18.txt 10 ms 1152 KB
19.txt 20 ms 2304 KB
20.txt 1 ms 256 KB
21.txt 12 ms 1280 KB
22.txt 22 ms 2560 KB
23.txt 20 ms 2304 KB
24.txt 1 ms 256 KB
25.txt 26 ms 2944 KB
26.txt 1 ms 256 KB
27.txt 1 ms 256 KB
28.txt 11 ms 1280 KB
29.txt 22 ms 2560 KB
30.txt 24 ms 2560 KB
31.txt 1 ms 256 KB
32.txt 30 ms 3456 KB
33.txt 1 ms 256 KB
34.txt 25 ms 2816 KB
35.txt 10 ms 1152 KB
36.txt 28 ms 3072 KB
37.txt 2 ms 256 KB
38.txt 11 ms 1280 KB
39.txt 22 ms 2432 KB
40.txt 1 ms 256 KB
41.txt 1 ms 256 KB
42.txt 1 ms 256 KB
43.txt 1 ms 256 KB
44.txt 1 ms 256 KB
45.txt 26 ms 2816 KB
46.txt 1 ms 256 KB
47.txt 1 ms 256 KB
48.txt 25 ms 2816 KB
49.txt 4 ms 512 KB
50.txt 1 ms 256 KB
51.txt 1 ms 256 KB
52.txt 1 ms 256 KB
s1.txt 1 ms 256 KB
s2.txt 1 ms 256 KB
s3.txt 1 ms 256 KB