Submission #14803918


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;

// 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';
            }
        }
    }


    // 貪欲に高いところから埋めていく.
    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;
        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(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;
                if(f[nx][ny] == 1)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++;
        }
    }
    

    // 出力
    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 799680
Code Size 3394 Byte
Status
Exec Time 25 ms
Memory 3724 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:89: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]
   89 |             if(keep.size() == K)break;
      |                ~~~~~~~~~~~~^~~~
./Main.cpp:103: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]
  103 |         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:115:5: note: in expansion of macro ‘rep’
  115 |     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:121:5: note: in expansion of macro ‘rep’
  121 |     rep(i,ans.size()) ofs << ans[i].first << ' ' << ans[i].second << endl;
      |     ^~~
./Main.cpp:34:13: warning: variable ‘start’ set but not used [-Wunused-but-set-variable]
   34 |     clock_t start,end;
      |             ^~~~~
./Main.cpp:34:19: warning: variable ‘end’ set but not used [-Wunused-but-set-variable]
   34 |     clock_t start,end;
      |                   ^~~

Judge Result

Set Name Score / Max Score Test Cases
test_01 74448 / 1343058 subtask_01_01.txt
test_02 75675 / 1343058 subtask_01_02.txt
test_03 83664 / 1343058 subtask_01_03.txt
test_04 76224 / 1343058 subtask_01_04.txt
test_05 89501 / 1343058 subtask_01_05.txt
test_06 77602 / 1343058 subtask_01_06.txt
test_07 80629 / 1343058 subtask_01_07.txt
test_08 72158 / 1343058 subtask_01_08.txt
test_09 85496 / 1343058 subtask_01_09.txt
test_10 84283 / 1343058 subtask_01_10.txt
Case Name Status Exec Time Memory
subtask_01_01.txt 19 ms 3724 KB
subtask_01_02.txt 17 ms 3600 KB
subtask_01_03.txt 20 ms 3600 KB
subtask_01_04.txt 16 ms 3708 KB
subtask_01_05.txt 17 ms 3544 KB
subtask_01_06.txt 20 ms 3600 KB
subtask_01_07.txt 15 ms 3664 KB
subtask_01_08.txt 15 ms 3704 KB
subtask_01_09.txt 16 ms 3684 KB
subtask_01_10.txt 25 ms 3508 KB