Submission #1191962


Source Code Expand

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

#define REP(i,n) for(ll i=0; i<(ll)(n); i++)
#define FOR(i,n,m) for (ll i=n; i<(ll)(m); i++)
#define pb push_back
#define INF 1000000007LL
#define all(a) (a).begin(),(a).end()
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)

typedef long long ll;
typedef pair<int,int> p;

int dy[4]={-1,1,0,0};
int dx[4]={0,0,1,-1};
int H, W, K;
string field[60];
int used[60][60];


struct node {
    int y, x, spec;
    bool operator<( const node& r ) const {
        if (spec == r.spec && y == r.y) {
            return x < r.x;
        }
        if (spec == r.spec) {
            return y < r.y;
        }
        return spec < r.spec;
    }
    bool operator==( const node& r ) const {
        return y == r.y && x == r.x;
    }
    bool operator!=( const node& r ) const {
        return y != r.y || x != r.x;
    }
};

map<node, node> par;
node last;

bool isOk(map<int,map<int,int> > &tmp_used, node n) {
    // 範囲外
    if (n.x < 0 || W <= n.x || n.y < 0 || H <= n.y) {
        return false;
    }
    // 使用された or 数字がゼロ
    if (tmp_used[n.y][n.x] || used[n.y][n.x] || field[n.y][n.x]=='0') {
        return false;
    }
    
    return true;
}

int value(vector<node> &a) {
    int ans = 1;
    for (node x: a) {
        ans *= x.spec;
    }
    return ans;
}

bool search(node n, int depth, map<int,map<int,int> > &tmp_used) {
    if (depth==K) {
        last = n;
        return true;
    }
    priority_queue<node> q;
    REP(i, 4) {
        int ny = n.y + dy[i];
        int nx = n.x + dx[i];
        node nex = node{ny,nx,0};
        if (isOk(tmp_used, nex)) {
            nex.spec = field[ny][nx]-'0';
            q.push(nex);
        }
    }
    vector<vector<node> > ans;
    while(!q.empty()) {
        node nex = q.top();q.pop();
        par[nex] = n;
        map<int,map<int,int> > tu = tmp_used;
        tu[nex.y][nex.x] = 1;
        // cout << n.y << ", " << n.x << " to " << nex.y << ", " << nex.x << endl;
        if (search(nex, depth+1, tu)){
            if(depth >= 8) {return true;}
            else {
                node tpre = last;
                vector<node> tans;
                REP(i,K) {
                    tans.pb(tpre);
                    tpre = par[tpre];
                }
                ans.pb(tans);
            }
        }
    }
    int mans = 0;
    for(vector<node> a:ans) {
        int t = value(a);
        if (mans < t) {
            mans = t;
            last = a[0];
            REP(i, K-1) {
                par[a[i]] = a[i+1];
            }
        }
    }
    if (mans) return true;
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin >> H >> W >> K;
    priority_queue<node> q;
    REP(i, H) {
        cin >> field[i];
        REP(j, W) q.push(node{(int)i,(int)j,field[i][j]-'0'});
    }
    vector< set<node> > lans;
    while(!q.empty()) {
        node a = q.top();q.pop();
        if (used[a.y][a.x]) continue;
        set<node> ans;
        map<int,map<int,int> > tu;
        tu[a.y][a.x] = 1;
        if (search(a,1,tu)) {
            REP(i,K) {
                ans.insert(last);
                used[last.y][last.x] = 1;
                last = par[last];
            }
            lans.pb(ans);
        }
    }
    cout << lans.size() << endl;
    for (set<node> &sn: lans) {
        for (node n: sn) {
            cout << n.y+1 << " " << n.x+1 << endl;
        }
    }
    return 0;
}

Submission Info

Submission Time
Task A - Multiple Pieces
User yush1ga
Language C++14 (GCC 5.4.1)
Score 557656
Code Size 3589 Byte
Status AC
Exec Time 211 ms
Memory 764 KB

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10
Score / Max Score 53084 / 1343058 51784 / 1343058 57394 / 1343058 53145 / 1343058 63401 / 1343058 50896 / 1343058 61880 / 1343058 54856 / 1343058 53936 / 1343058 57280 / 1343058
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 173 ms 764 KB
subtask_01_02.txt AC 200 ms 640 KB
subtask_01_03.txt AC 197 ms 640 KB
subtask_01_04.txt AC 211 ms 640 KB
subtask_01_05.txt AC 209 ms 640 KB
subtask_01_06.txt AC 189 ms 640 KB
subtask_01_07.txt AC 197 ms 640 KB
subtask_01_08.txt AC 204 ms 640 KB
subtask_01_09.txt AC 192 ms 640 KB
subtask_01_10.txt AC 172 ms 640 KB