Submission #14803432


Source Code Expand

Copy
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005
#define MAX_H 60
#define MAX_W 60

    /*
    いろいろ
    int x = rand()%100;
    double x = (double)rand()/RAND_MAX;
    mt19937 get_rand_mt;
    shuffle(vec.begin(), vec.end(), get_rand_mt);
    */

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

int H, W, K;
int a[MAX_H][MAX_W];
int f[MAX_H][MAX_W];

vector<P> ans;
int ans_cnt;

int check(int x, int y){
    rep(i,4){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx <= 0 || H < nx || ny <= 0 || W <= ny){
            continue;
        }
        if(f[nx][ny] == 1){
            return 0;
        }
    }
    return 1;
}

// 1-index
int main() {
    srand((unsigned) time(NULL));
    clock_t start,end;
	start = clock();

    string fileNameIfs = "sample_in.txt";
    const char* cstrIfs = fileNameIfs.c_str();
    ifstream ifs(cstrIfs);
    if(!ifs.is_open()){ // 標準入力する
        cin >> H >> W >> K;
        srep(i,1,H+1){
            srep(j,1,W+1){
                char c; cin >> c;
                a[i][j] = c - '0';
            }
        }
    }else{ // ファイル入力する
        ifs >> H >> W >> K;
        srep(i,1,H+1){
            srep(j,1,W+1){
                char c; ifs >> c;
                a[i][j] = c - '0';
            }
        }
    }

    /*
    // 市松に入れてみる.
    srep(i,1,H+1){
        rep(j,W/K){
            if(i%2 == j%2){
                rep(k,K){
                    f[i][1+j*K+k] = 1;
                }
            }
        }
    }
    */



    // 貪欲に高いところから埋めていく.
    priority_queue<pair<int,P>> que;
    pair<int,P> p;
    srep(i,1,H+1){
        srep(j,1,W+1){
            p.first = a[i][j];
            p.second.first = i;
            p.second.second = j;
            que.push(p);
        }
    }
    
    while(que.size() > 0){
        int x = que.top().second.first;
        int y = que.top().second.second;
        // cout << x << ' ' << y << endl;
        que.pop();
        if(f[x][y] == 1)continue;
        set<P> keep, seen;
        priority_queue<pair<int,P>> q;
        p.first = a[x][y];
        p.second.first = x;
        p.second.second = y;
        q.push(p);
        seen.insert(P(x,y));
        while(q.size() > 0){
            x = q.top().second.first;
            y = q.top().second.second;
            q.pop();
            if(check(x,y) == 0) continue;
            if(a[x][y] == 0)break;
            keep.insert(P(x,y));
            if(keep.size() == K)break;
            rep(i,4){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx <= 0 || H < nx || ny <= 0 || W < ny) continue;
                if(seen.find(P(nx,ny)) != seen.end()) continue;
                p.first = a[nx][ny];
                p.second.first = nx;
                p.second.second = ny;
                q.push(p);
                seen.insert(P(nx,ny));
            }
        }
        if(keep.size() == K){
            for (P pp : keep){
                f[pp.first][pp.second] = 1;
                ans.push_back(P(pp.first, pp.second));
            }
            ans_cnt++;
        }
    }
    

    // 出力
    /*
    rep(i,MAX_H){
        rep(j,MAX_W){
            if(f[i][j] != 0){
                ans.push_back(P(i,j));
            }
        }
    }
    cout << ans.size() / K << endl;
    */
    cout << ans_cnt << endl;
    rep(i,ans.size()) cout << ans[i].first << ' ' << ans[i].second << endl;


    string fileName = "sample_out.txt";
    const char* cstr = fileName.c_str();
    ofstream ofs(cstr);
    ofs << ans_cnt << endl;
    rep(i,ans.size()) ofs << ans[i].first << ' ' << ans[i].second << endl;
    ofs.close();

    end = clock();
    return 0;
}
 
 

Submission Info

Submission Time
Task A - Multiple Pieces
User Shibuyap
Language C++ (GCC 9.2.1)
Score 130753
Code Size 4156 Byte
Status
Exec Time 19 ms
Memory 3680 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:119:28: warning: comparison of integer expressions of different signedness: ‘std::set<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  119 |             if(keep.size() == K)break;
      |                ~~~~~~~~~~~~^~~~
./Main.cpp:132:24: warning: comparison of integer expressions of different signedness: ‘std::set<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} and ‘int’ [-Wsign-compare]
  132 |         if(keep.size() == K){
      |            ~~~~~~~~~~~~^~~~
./Main.cpp:2:35: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
    2 | #define rep(i,n) for(int i = 0; i < (n); ++i)
      |                                   ^
./Main.cpp:154:5: note: in expansion of macro ‘rep’
  154 |     rep(i,ans.size()) cout << ans[i].first << ' ' << ans[i].second << endl;
      |     ^~~
./Main.cpp:2:35: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<std::pair<int, int> >::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
    2 | #define rep(i,n) for(int i = 0; i < (n); ++i)
      |                                   ^
./Main.cpp:161:5: note: in expansion of macro ‘rep’
  161 |     rep(i,ans.size()) ofs << ans[i].first << ' ' << ans[i].second << endl;
      |     ^~~
./Main.cpp:48:13: warning: variable ‘start’ set but not used [-Wunused-but-set-variable]
   48 |     clock_t start,end;
      |             ^~~~~
./Main.cpp:48:19: warning: variable ‘end’ set but not used [-Wunused-but-set-variable]
   48 |     clock_t start,end;
      |                   ^~~

Judge Result

Set Name Score / Max Score Test Cases
test_01 66530 / 1343058 subtask_01_01.txt
test_02 0 / 1343058 subtask_01_02.txt
test_03 0 / 1343058 subtask_01_03.txt
test_04 0 / 1343058 subtask_01_04.txt
test_05 0 / 1343058 subtask_01_05.txt
test_06 64223 / 1343058 subtask_01_06.txt
test_07 0 / 1343058 subtask_01_07.txt
test_08 0 / 1343058 subtask_01_08.txt
test_09 0 / 1343058 subtask_01_09.txt
test_10 0 / 1343058 subtask_01_10.txt
Case Name Status Exec Time Memory
subtask_01_01.txt 16 ms 3592 KB
subtask_01_02.txt 15 ms 3540 KB
subtask_01_03.txt 12 ms 3544 KB
subtask_01_04.txt 12 ms 3516 KB
subtask_01_05.txt 11 ms 3588 KB
subtask_01_06.txt 15 ms 3680 KB
subtask_01_07.txt 16 ms 3676 KB
subtask_01_08.txt 12 ms 3536 KB
subtask_01_09.txt 19 ms 3668 KB
subtask_01_10.txt 12 ms 3644 KB