Submission #555986

#TimeUsernameProblemLanguageResultExecution timeMemory
555986AriaHSuper Dango Maker (JOI22_dango3)C++17
22 / 100
1171 ms592 KiB
/* Im the best and i work like that */ #pragma GCC optimize("Ofast") #include "dango3.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair < int, int > pii; typedef pair < ll, ll > pll; #define F first #define S second #define all(x) x.begin(),x.end() #define Mp make_pair #define point complex #define endl '\n' #define SZ(x) (int)x.size() #define fast_io ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define file_io freopen("input.txt", "r+", stdin); freopen("output.txt", "w+", stdout); #define mashtali return cout << "Hello, World!", 0; const int N = 1e4 + 10; const int LOG = 20; const ll mod = 1e9 + 7; const ll inf = 8e18; const double pi = acos(-1); const ld eps = 1e-18; const ld one = 1.; ll pw(ll a, ll b, ll M, ll ret = 1) { if(a == 0) return 0; a %= M; while(b) { ret = (b & 1? ret * a % M : ret), a = a * a % M, b >>= 1; } return ret % M; } mt19937 rng(time(nullptr)); int n, m, id[N], B[N]; inline int ask() { ///printf("asking : \n"); vector < int > vec; for(int i = 1; i <= n * m; i ++) { if(B[i]) vec.push_back(id[i]); } /*for(auto x : vec) { printf("%d ", x); } */ int ret = (SZ(vec) < n? 0 : Query(vec)); ///printf("ans : %d\n", ret); return ret; } void _Answer(vector < int > vec) { vector < int > ret; for(auto x : vec) ret.push_back(id[x]); Answer(ret); } vector < int > EXT(vector < int > vec) { if(SZ(vec) < n) return vec; memset(B, 0, sizeof B); vector < int > ret, out; for(int i = 0; i < SZ(vec); i ++) { B[vec[i]] = 1; } for(int i = 0; i < SZ(vec); i ++) { B[vec[i]] = 0; if(ask()) { ret.push_back(vec[i]); } else { out.push_back(vec[i]); B[vec[i]] = 1; } } memset(B, 0, sizeof B); for(auto x : ret) B[x] = 1; _Answer(out); return ret; } void Solve(int _n, int _m) { n = _n; m = _m; for(int i = 1; i <= n * m; i ++) { id[i] = i; } shuffle(id + 1, id + n * m + 1, rng); int ptr = 1; vector < int > vec; int q = m; while(q --) { while(ask() == 0) { ///printf("ptr = %d\n", ptr); B[ptr] = 1; vec.push_back(ptr); ptr ++; } if(q == 0) { _Answer(vec); return; } vec = EXT(vec); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...