oj.uz

Submission #596819

# Submission time Handle Problem Language Result Execution time Memory
596819 2022-07-15T06:49:33 Z 박상훈(#8446) Super Dango Maker (JOI22_dango3) C++17
7 / 100
 10000 ms 644 KB 
#include "dango3.h"

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

namespace {

int n, m;
mt19937 seed(123678);
vector<int> P;
set<int> st[505];

}  // namespace

int my_query(vector<int> v){
    for (auto &x:v) x = P[x-1];
    return Query(v);
}

void my_ans(){
    vector<int> ans;
    for (int i=1;i<=m;i++){
        for (int j=1;j<=n;j++){
            ans.push_back(P[*st[j].begin()-1]);
            st[j].erase(st[j].begin());
        }
        Answer(ans);
        ans.clear();
    }
}

void chk(int col, int val){
    if (st[col].size()==m) return;
    vector<int> Q;
    for (int i=1;i<=n*m;i++){
        if (st[col].find(i)!=st[col].end()) continue;
        if (i==val) continue;
        Q.push_back(i);
    }

    if (my_query(Q)!=m - (int)st[col].size()){
        st[col].insert(val);
    }
}

bool solve(vector<int> &cur, int s, int e, int col){
    if (st[col].size()==m) return 0;
    if (e>(int)cur.size()) return 1;

    vector<int> Q;
    for (int i=1;i<=n*m;i++){
        if (st[col].find(i)!=st[col].end()) continue;
        int idx = lower_bound(cur.begin(), cur.end(), i) - cur.begin();
        if (idx<(int)cur.size() && cur[idx]==i && idx>=s && idx<e) continue;

        Q.push_back(i);
    }

    int ret = my_query(Q);
    if (ret==m-(int)st[col].size()-(e-s)){
        for (int i=s;i<e;i++) st[col].insert(cur[i]);
        return 0;
    }
    return ret != m - (int)st[col].size();
}

void Solve(int N, int M) {
    n = N, m = M;

    vector<int> cur;
    for (int i=1;i<=N*M;i++) cur.push_back(i);
    P = cur;
    shuffle(P.begin(), P.end(), seed);

    for (int i=1;i<=N;i++){
        if (i==N){
            for (auto &x:cur) st[i].insert(x);
            break;
        }

        st[i].insert(cur[0]);

        for (int j=1;j<(int)cur.size();){
            int r = j + st[i].size();
            //printf(" %d -> %d\n", j, r);

            if (solve(cur, j, r, i)){
                //printf(" Yes %d %d\n", j, r);
                for (int k=j;k<r;k++) chk(i, cur[k]);
            }

            j = r;
        }

        vector<int> nxt;
        for (auto &x:cur) if (st[i].find(x)==st[i].end()) nxt.push_back(x);
        swap(cur, nxt);

        //printf("col #%d ok\n", i);
    }

    my_ans();
}

Compilation message

dango3.cpp: In function 'void chk(int, int)':
dango3.cpp:33:23: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   33 |     if (st[col].size()==m) return;
      |         ~~~~~~~~~~~~~~^~~
dango3.cpp: In function 'bool solve(std::vector<int>&, int, int, int)':
dango3.cpp:47:23: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |     if (st[col].size()==m) return 0;
      |         ~~~~~~~~~~~~~~^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 539 ms 404 KB Output is correct
2 Correct 533 ms 420 KB Output is correct
3 Correct 543 ms 520 KB Output is correct
4 Correct 529 ms 424 KB Output is correct
5 Correct 569 ms 524 KB Output is correct
6 Correct 564 ms 448 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 9331 ms 584 KB Wrong Answer [3]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 78.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10090 ms 644 KB Time limit exceeded
2 Halted 0 ms 0 KB -