oj.uz

Submission #715121

# Submission time Handle Problem Language Result Execution time Memory
715121 2023-03-25T23:05:57 Z justinhall363 Carnival (CEOI14_carnival) C++14
20 / 100
 102 ms 328 KB 
#include <iostream>
#include <vector>
#include <set>
#include <map>

using namespace::std;
#define FOR(i, b) for(int i = 0; i < b; i++)
#define F0R(i, a, b) for(int i = a; i <= b; i++)
int N;
vector<int> e;
int get(int x){ return e[x] < 0 ? x : e[x] = get(e[x]); }
void unite(int x, int y){
    x = get(x), y = get(y);
    if(x == y) return;
    if(e[x] > e[y]) swap(x, y);
    e[x] += e[y];
    e[y] = x;
}

int query(int i0, int iN){ //ask grader how many
    cout<<iN-i0+1<<" ";
    F0R(i, i0, iN-1) cout<<i+1<<" "; cout<<iN+1<<endl;
    int diff; cin>>diff; return diff;
}

void check(int i0, int iN){ //i limits inclusive
    if(i0 == iN) return; //only 1
    int diff = query(i0, iN);
    if(diff == 1){ //all same costume
        F0R(i, i0+1, iN) unite(i0, i); 
        return;
    }  
    if(iN-i0 == 1) return; //2 left don't need to check

    //split in half
    int half = i0+(iN-i0)/2;
    check(i0, half); check(half+1, iN); 
    set<int> cc1, cc2; //cc reps of first half and second half
    F0R(i, i0, half) cc1.insert(get(i));
    F0R(i, half+1, iN) cc2.insert(get(i));

    vector<int> used(N);
    for(int c1 : cc1){ //check for overlaps
        for(int c2 : cc2){
            if(c1 == c2 || used[c2]) continue;
            cout<<2<<" "<<c1+1<<" "<<c2+1<<endl;
            int q; cin>>q; 
            if(q == 1){ unite(c1, c2); used[c1] = true; used[c2] = true; break; } //found same costume
        }
    }
}

int main() {
    //freopen("carnival.in", "r", stdin);
    //freopen("carnival.out", "w", stdout);
    cin>>N;
    e = vector<int>(N, -1);
    check(0, N-1);

    //convert to costume #s
    map<int, int> cc; int id = 1;
    FOR(i, N) if(e[i] < 0){ cc[i] = id; id++; }
    cout<<0<<" "; FOR(i, N) cout<<cc[get(i)]<<" "; cout<<endl;
}

Compilation message

carnival.cpp: In function 'int query(int, int)':
carnival.cpp:8:22: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
    8 | #define F0R(i, a, b) for(int i = a; i <= b; i++)
      |                      ^~~
carnival.cpp:22:5: note: in expansion of macro 'F0R'
   22 |     F0R(i, i0, iN-1) cout<<i+1<<" "; cout<<iN+1<<endl;
      |     ^~~
carnival.cpp:22:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   22 |     F0R(i, i0, iN-1) cout<<i+1<<" "; cout<<iN+1<<endl;
      |                                      ^~~~

Subtask #1
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 296 KB Output is correct
2 Correct 19 ms 208 KB Output is correct
3 Partially correct 60 ms 280 KB Partially correct
4 Partially correct 94 ms 296 KB Partially correct
5 Correct 3 ms 208 KB Output is correct
6 Correct 1 ms 208 KB Output is correct
7 Correct 24 ms 208 KB Output is correct

Subtask #2
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 208 KB Output is correct
2 Correct 21 ms 296 KB Output is correct
3 Partially correct 41 ms 304 KB Partially correct
4 Partially correct 102 ms 296 KB Partially correct
5 Correct 5 ms 208 KB Output is correct
6 Correct 2 ms 208 KB Output is correct
7 Correct 8 ms 208 KB Output is correct

Subtask #3
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 7 ms 208 KB Output is correct
3 Partially correct 41 ms 208 KB Partially correct
4 Partially correct 44 ms 296 KB Partially correct
5 Correct 7 ms 300 KB Output is correct
6 Correct 14 ms 208 KB Output is correct
7 Correct 21 ms 208 KB Output is correct

Subtask #4
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 208 KB Output is correct
2 Correct 5 ms 208 KB Output is correct
3 Partially correct 77 ms 288 KB Partially correct
4 Partially correct 86 ms 328 KB Partially correct
5 Correct 12 ms 208 KB Output is correct
6 Correct 27 ms 208 KB Output is correct
7 Correct 24 ms 208 KB Output is correct

Subtask #5
4.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 208 KB Output is correct
2 Correct 12 ms 208 KB Output is correct
3 Partially correct 42 ms 208 KB Partially correct
4 Partially correct 54 ms 208 KB Partially correct
5 Partially correct 30 ms 208 KB Partially correct
6 Partially correct 68 ms 300 KB Partially correct
7 Partially correct 81 ms 284 KB Partially correct