oj.uz

Submission #585910

# Submission time Handle Problem Language Result Execution time Memory
585910 2022-06-29T14:28:09 Z MilosMilutinovic Zagrade (COI20_zagrade) C++14
100 / 100
 888 ms 1636 KB 
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;
 
#ifdef LOCAL
	#define eprintf(...) {fprintf(stderr, __VA_ARGS__);fflush(stderr);}
#else
	#define eprintf(...) 42
#endif
 
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull = unsigned long long;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
	return (ull)rng() % B;
}
 
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
 
clock_t startTime;
double getCurrentTime() {
	return (double)(clock() - startTime) / CLOCKS_PER_SEC;
}

const int N = 100100;
char ans[N]; 

int Ask(int l, int r) {
	printf("? %d %d\n", l, r);
	fflush(stdout);
	int x;
	scanf("%d", &x);
	return x;
}

int main() 
{
	startTime = clock();
//	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
	
	int n, q;
	scanf("%d%d", &n, &q);
	vector<int> stk;
	for (int i = 1; i <= n; i++)
		ans[i] = '!';
	for (int i = 1; i <= n; i++) {
		if (stk.empty() || !Ask(stk.back(), i)) 
			stk.push_back(i);
		else {
			ans[stk.back()] = '(';
			ans[i] = ')';
			stk.pop_back();
		}
	}
	vector<int> pos;
	for (int i = 1; i <= n; i++)
		if (ans[i] == '!')
			pos.push_back(i);
	int sz = (int)pos.size();
	for (int i = 0; i < sz; i++)
		ans[pos[i]] = (i < sz / 2 ? ')' : '(');
	printf("! ");
	for (int i = 1; i <= n; i++) 
		printf("%c", ans[i]);
	fflush(stdout);

	return 0;
}

Compilation message

zagrade.cpp: In function 'int Ask(int, int)':
zagrade.cpp:61:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |  scanf("%d", &x);
      |  ~~~~~^~~~~~~~~~
zagrade.cpp: In function 'int main()':
zagrade.cpp:72:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |  scanf("%d%d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

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

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 11 ms 208 KB Output is correct
3 Correct 8 ms 208 KB Output is correct
4 Correct 7 ms 208 KB Output is correct
5 Correct 9 ms 208 KB Output is correct
6 Correct 9 ms 312 KB Output is correct
7 Correct 7 ms 208 KB Output is correct
8 Correct 6 ms 208 KB Output is correct

Subtask #3
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 415 ms 380 KB Output is correct
3 Correct 750 ms 336 KB Output is correct
4 Correct 667 ms 336 KB Output is correct
5 Correct 767 ms 384 KB Output is correct
6 Correct 748 ms 336 KB Output is correct
7 Correct 880 ms 820 KB Output is correct
8 Correct 409 ms 336 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 867 ms 1636 KB Output is correct
3 Correct 888 ms 612 KB Output is correct
4 Correct 453 ms 1056 KB Output is correct
5 Correct 769 ms 756 KB Output is correct
6 Correct 740 ms 1084 KB Output is correct
7 Correct 733 ms 728 KB Output is correct
8 Correct 702 ms 376 KB Output is correct