oj.uz

Submission #1097632

# Submission time Handle Problem Language Result Execution time Memory
1097632 2024-10-07T17:23:46 Z FIFI_cpp Zagrade (COI20_zagrade) C++17
21 / 100
 3000 ms 344 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <deque>
#include <fstream>
#include <iterator>
#include <set>
#include <map>
#include <unordered_map>
#include <iomanip>
#include <cctype>
#include <string>
#include <cassert>
#include <set>
#include <bitset>
#include <unordered_set>
#include <numeric>
using ll = int64_t;
#define pb push_back
#define all(a) a.begin(),a.end()
#define ppi pair<int,pair<int,int>>
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
//#define int int64_t
// xcode cant include bits/stdc++.h
using namespace std;
/*   /\_/\
*   (= ._.)
*   / >  \>
*/
// encouraging cat
//const int INF = 10000000000000000;
//const int mod = 1000000007;
const int mod = 1000000007;
const int MAXN = 2003;
//const int INF = 10000000000000000;
//ifstream fin("fractii2.in");
//ofstream fout("fractii2.out");
map<pair<int,int>,bool> mp;
bool valid_walk(int l,int r)
{
    l++,r++;
    cout << "? " << l << " " << r << '\n';
    cout.flush();
    bool x;
    cin >> x;
    return x;
}
int32_t main()
{
    int n,q;
    cin >> n >> q;
    vector<bool> del(n);
    auto kth_non_del = [&](int k) {
        for (int i = 0;i < n;i++)
        {
            if (del[i])
            {
                continue;
            }
            if (k == 0)
            {
                return i;
            }
            k--;
        }
        return -1;
    };
 
    string s;
    s.resize(n);
 
    int i = 0, d = 0;
    while (i < n - d - 1) {
        int a = kth_non_del(i), b = kth_non_del(i + 1);
        //cout << "? " << a + 1 << ' ' << b + 1 << endl;
        if (valid_walk(a, b))
        {
            del[a] = del[b] = true;
            d += 2;
            s[a] = 'U';
            s[b] = 'D';
            if (i > 0)
                i--;
        }
        else
        {
            i++;
        }
        
    }
    int cnt = (n - d) / 2;
    for (int i = 0;i < n;i++)
    {
        if (del[i])
        {
            continue;
        }
        if (cnt > 0)
        {
            s[i] = 'D';
            cnt--;
        }
        else
        {
            s[i] = 'U';
        }
    }
    cout << "! ";
    for (int i = 0;i < n;i++)
    {
        if (s[i] == 'U')
            cout << "(";
        else
            cout << ")";
    }
    cout << '\n';
    cout.flush();
    return 0;
}

Compilation message

zagrade.cpp:31:9: warning: "/*" within comment [-Wcomment]
   31 | /*   /\_/\
      |

Subtask #1
14.0 / 14.0

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

Subtask #2
7.0 / 7.0

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

Subtask #3
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Execution timed out 3013 ms 344 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Execution timed out 3068 ms 344 KB Time limit exceeded
3 Halted 0 ms 0 KB -