oj.uz

Submission #598853

# Submission time Handle Problem Language Result Execution time Memory
598853 2022-07-19T06:30:41 Z Arnch Super Dango Maker (JOI22_dango3) C++17
100 / 100
 1304 ms 844 KB 
// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
#include "dango3.h"
//#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
//#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl

constexpr ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969;

int n, m;
bool mark[N], vis[N];

void dojob(vector<int> vc) {
	if(Sz(vc) == n) {
		Answer(vc);
		return;
	}
	int mid = (Sz(vc) / n) >> 1;
	vector<int> ans, ans2;
	for(auto i : vc) vis[i] = mark[i] = 0;
	int tim = Sz(vc) / n;
	while(Sz(ans) != n * mid) {
		vector<int> ad;
		int x = -1;
		for(auto i : vc) {
			if(!mark[i]) {
				if(x == -1 && !vis[i]) {
					x = i;
					vis[i] = 1;
					continue;
				}
				ad.push_back(i);
			}
		}
		int cur = Query(ad);
		if(cur >= (tim - mid)) {
			mark[x] = 1;
			ans.push_back(x);
		}
	}
	for(auto i : vc) {
		if(!mark[i]) ans2.push_back(i);
	}
	dojob(ans), dojob(ans2);
}

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

	vector<int> vc;
	for(int i = 1; i <= n * m; i++) vc.push_back(i);
	dojob(vc);


}

Subtask #1
2.0 / 2.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 388 KB Output is correct
2 Correct 12 ms 400 KB Output is correct
3 Correct 15 ms 340 KB Output is correct
4 Correct 15 ms 400 KB Output is correct
5 Correct 9 ms 316 KB Output is correct
6 Correct 9 ms 400 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 492 KB Output is correct
2 Correct 262 ms 540 KB Output is correct
3 Correct 340 ms 636 KB Output is correct
4 Correct 345 ms 468 KB Output is correct
5 Correct 177 ms 528 KB Output is correct
6 Correct 183 ms 512 KB Output is correct

Subtask #4
78.0 / 78.0

# Verdict Execution time Memory Grader output
1 Correct 1041 ms 644 KB Output is correct
2 Correct 1078 ms 720 KB Output is correct
3 Correct 1296 ms 696 KB Output is correct
4 Correct 1304 ms 736 KB Output is correct
5 Correct 713 ms 844 KB Output is correct
6 Correct 694 ms 712 KB Output is correct