oj.uz

Submission #972696

# Submission time Handle Problem Language Result Execution time Memory
972696 2024-05-01T01:41:38 Z hotboy2703 Super Dango Maker (JOI22_dango3) C++17
100 / 100
 2216 ms 1112 KB 
#include "dango3.h"

#include <bits/stdc++.h>
using ll = int;
using namespace std;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL<<(i))
#define sz(a) (ll((a).size()))
namespace {
    vector <ll> ans[26];
    mt19937_64 rng(69420);
    bool in[10010];
}
void f(){}
void Solve(int n,int m) {
    auto alldif = [&](vector <ll> x) -> bool{
        if (sz(x) < 2)return 1;
        for (auto y:x)in[y] = 1;
        vector <ll> tmp;
        for (ll i = 1;i <= n * m;i ++)(in[i]) ? f() :tmp.push_back(i);
        for (auto y:x)in[y] = 0;
//        cout<<"ALLDIF\n";
//        for (auto y:x)cout<<y<<' ';
//        cout<<'\n';
//        for (auto y:tmp)cout<<y<<' ';
//        cout<<'\n';
        return (Query(tmp)== m - 1);
    };
    for (ll i = 1;i <= n * m;i ++){
        ll l = 1;
        ll r = m;
        ll res;
        while (l <= r){
            ll mid = (l + r) >> 1;
            ans[mid].push_back(i);
//            cout<<"FIND "<<l<<' '<<r<<' '<<mid<<'\n';
            if (alldif(ans[mid])){
                res = mid;
                r = mid - 1;
            }
            else{
                l = mid + 1;
            }
            ans[mid].pop_back();
        }
//        cout<<"ANS "<< i<<' '<<res<<'\n';
        ans[res].push_back(i);
    }
//    for (ll i = 1;i <= m;i ++){for (auto x:ans[i])cout<<x<<' ';cout<<'\n';}
    for (ll i = 1;i <= m;i ++)Answer(ans[i]);
}

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 520 KB Output is correct
2 Correct 15 ms 344 KB Output is correct
3 Correct 15 ms 348 KB Output is correct
4 Correct 16 ms 348 KB Output is correct
5 Correct 12 ms 520 KB Output is correct
6 Correct 15 ms 348 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 459 ms 880 KB Output is correct
2 Correct 447 ms 616 KB Output is correct
3 Correct 552 ms 604 KB Output is correct
4 Correct 550 ms 636 KB Output is correct
5 Correct 389 ms 612 KB Output is correct
6 Correct 389 ms 604 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 1834 ms 1112 KB Output is correct
2 Correct 1823 ms 880 KB Output is correct
3 Correct 2216 ms 980 KB Output is correct
4 Correct 2195 ms 996 KB Output is correct
5 Correct 1510 ms 996 KB Output is correct
6 Correct 1479 ms 852 KB Output is correct