oj.uz

Submission #886166

# Submission time Handle Problem Language Result Execution time Memory
886166 2023-12-11T14:18:09 Z vjudge1 Toxic Gene (NOI23_toxic) C++17
41.8588 / 100
 8 ms 600 KB 
#include "toxic.h"
#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define sp " "
#define endl "\n"
#define pii pair<int, int>
#define st first
#define nd second
#define pb push_back
#define LOGN 8


void query(vector<int> &v, vector<int> &ans){
    if (v.size() == 1){
        ans.pb(v.back());
        return;
    }
    int t = -1;
    for (int i = 2; i >= 0; i--){
        int tmp = t + (1<<i);
        if (tmp + 1 < v.size()){
            vector<int> gh;
            for (int i = 0; i <= tmp; i++) gh.pb(v[i]);
            if (query_sample(gh) == gh.size()) t = tmp;
        }
    }
    t++;
    ans.pb(v[t]);
    vector<int> nv;
    for (int i = t + 1; i < v.size(); i++) nv.pb(v[i]);
    if (query_sample(nv) != nv.size()) query(nv, ans);
}

void determine_type(int n){
    vector<int> type(n + 5);
    int t = 1;
    for (int i = LOGN; i >= 0; i--){
        int tmp = t + (1<<i);
        if (tmp <= n){
            vector<int> v;
            for (int i = 1; i <= tmp; i++) v.pb(i);
            if (query_sample(v) == v.size()) t = tmp;
        }
    }

    vector<int> v;
    if (t == 1){
        v.pb(t);
        if (query_sample(v) != 0) t++; 
    }
    else{
        t++;
    }
    //cout<<q[current_tc]<<sp;
    //cout<<t<<endl;
    type[t] = 1;
    for (int i = 1; i <= n; i += 8){
        vector<int> v;
        int e = min(8, n - i + 1);
        for (int j = 0; j < e; j++){
            for (int k = 1; k <= (1<<j); k++)
                v.pb(i + j);
        }
        if (t < i || t >= i + e) v.pb(t);
        int sum = (1<<e) - 1;
        int res = query_sample(v);
        //for (auto i : v) cout<<i<<sp;
        //cout<<": "<<res<<endl;
        for (int j = 0; j < e; j++){
            if ((res & (1<<j))) type[i + j] = 2;
        }
    }
    
    //cout<<q[current_tc]<<sp;

    for (int i = 1; i <= n; i += 8){
        vector<int> v;
        for (int j = 0; j < min(8, n - i + 1); j++){
            v.pb(i + j);
        }
        int res = query_sample(v);
        if (res != v.size()){
            vector<int> ans;
            query(v, ans);
            for (auto i : ans) type[i] = 1;
        }
    }

    //cout<<q[current_tc]<<endl;
    for (int i = 1; i <= n; i++){
        if (type[i] == 0) answer_type(i, 'R');
        else if (type[i] == 1) answer_type(i, 'T');
        else answer_type(i, 'S');
    }
} 
/*
namespace {
    static void wrong_answer(){
        printf("%d\n",-1);
        //exit(0);
    }
    static int tc, current_tc, N, batchsize = 300, qlimit = 600;
    static int q[105];
    static char answer[105][305];
    static char participant_type[105][305];
}

int query_sample(vector<int> species){
    if (species.size() > batchsize){
        cout<<"size exceeded"<<endl;
        wrong_answer();
    }
    q[current_tc]++;
    if (q[current_tc] > qlimit){
        cout<<"query limit exceeded"<<endl;
        wrong_answer();
    }
    bool has_toxic = false;
    int reg = 0, strong = 0;
    for (int i = 0; i < (int) species.size(); ++i){
        if (species[i] < 1 || species[i] > N){
            cout<<"specie id invalid"<<endl;
            wrong_answer();
        }
        char tp = answer[current_tc][species[i]];
        if (tp == 'T'){
            has_toxic = true;
        }
        if (tp == 'R'){
            reg++;
        }
        if (tp == 'S'){
            strong++;
        }
    }
    if (has_toxic) return strong;
    else return reg + strong;
}

void answer_type(int x, char c){
    //cout<<c<<sp;
    if (x < 1 || x > N) wrong_answer();
    if (c != 'T' && c != 'R' && c != 'S') wrong_answer(); 
    participant_type[current_tc][x] = c;
    if (participant_type[current_tc][x] != answer[current_tc][x]) wrong_answer();
}

int main(){
    fileio();
    assert(2 == scanf("%d %d\n",&tc,&N));
    for (int t = 1; t <= tc; ++t){
        assert(1 == scanf("%s",answer[t]));
        for (int i = N; i >= 1; --i){
            answer[t][i] = answer[t][i-1];
        }
        answer[t][0] = 'X';
        for (int i = 1; i <= N; ++i){
            participant_type[t][i] = 'X';
        }
    }
    for (int t = 1; t <= tc; ++t){
        current_tc = t;
        q[current_tc] = 0;
        determine_type(N);
        for (int i = 1; i <= N; ++i){
            if (participant_type[current_tc][i] != answer[current_tc][i]) wrong_answer();
        }
    }
    


    for (int t = 1; t <= tc; ++t){
        printf("%d\n",q[t]);
    }
    return 0;
    
}*/

Compilation message

toxic.cpp: In function 'void query(std::vector<int>&, std::vector<int>&)':
toxic.cpp:23:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         if (tmp + 1 < v.size()){
      |             ~~~~~~~~^~~~~~~~~~
toxic.cpp:26:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |             if (query_sample(gh) == gh.size()) t = tmp;
      |                 ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
toxic.cpp:32:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = t + 1; i < v.size(); i++) nv.pb(v[i]);
      |                         ~~^~~~~~~~~~
toxic.cpp:33:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     if (query_sample(nv) != nv.size()) query(nv, ans);
      |         ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~
toxic.cpp: In function 'void determine_type(int)':
toxic.cpp:44:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             if (query_sample(v) == v.size()) t = tmp;
      |                 ~~~~~~~~~~~~~~~~^~~~~~~~~~~
toxic.cpp:67:13: warning: unused variable 'sum' [-Wunused-variable]
   67 |         int sum = (1<<e) - 1;
      |             ^~~
toxic.cpp:84:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |         if (res != v.size()){
      |             ~~~~^~~~~~~~~~~

Subtask #1
41.85882353 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Partially correct 5 ms 344 KB Partially correct
3 Partially correct 5 ms 504 KB Partially correct
4 Partially correct 5 ms 348 KB Partially correct
5 Partially correct 6 ms 504 KB Partially correct
6 Partially correct 5 ms 348 KB Partially correct
7 Partially correct 7 ms 344 KB Partially correct
8 Partially correct 5 ms 348 KB Partially correct
9 Partially correct 6 ms 348 KB Partially correct
10 Partially correct 8 ms 348 KB Partially correct
11 Partially correct 6 ms 600 KB Partially correct
12 Partially correct 6 ms 348 KB Partially correct
13 Partially correct 5 ms 348 KB Partially correct
14 Partially correct 5 ms 348 KB Partially correct
15 Partially correct 5 ms 504 KB Partially correct
16 Partially correct 6 ms 348 KB Partially correct
17 Partially correct 6 ms 344 KB Partially correct
18 Partially correct 6 ms 500 KB Partially correct
19 Partially correct 6 ms 500 KB Partially correct
20 Partially correct 6 ms 348 KB Partially correct
21 Partially correct 7 ms 348 KB Partially correct
22 Partially correct 5 ms 348 KB Partially correct
23 Partially correct 7 ms 348 KB Partially correct
24 Partially correct 5 ms 348 KB Partially correct
25 Partially correct 5 ms 348 KB Partially correct
26 Partially correct 5 ms 348 KB Partially correct
27 Partially correct 5 ms 348 KB Partially correct
28 Partially correct 5 ms 348 KB Partially correct
29 Partially correct 5 ms 348 KB Partially correct
30 Partially correct 5 ms 348 KB Partially correct
31 Partially correct 6 ms 344 KB Partially correct
32 Partially correct 5 ms 348 KB Partially correct
33 Partially correct 5 ms 348 KB Partially correct
34 Partially correct 6 ms 504 KB Partially correct
35 Partially correct 5 ms 348 KB Partially correct
36 Partially correct 1 ms 348 KB Partially correct