oj.uz

Submission #246831

# Submission time Handle Problem Language Result Execution time Memory
246831 2020-07-10T11:53:05 Z egekabas Chameleon's Love (JOI20_chameleon) C++14
0 / 100
 40 ms 384 KB 
#include <bits/stdc++.h>
#include "chameleon.h"
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll>    pll;
typedef pair<ull, ull>    pull;
typedef pair<int, int>  pii;
typedef pair<ld, ld>  pld;
vector<int> pos[1009];
int ans[1009];
int okay(int x, int l, int r){
    vector<int> tmp;
    tmp.pb(x);
    for(int i = l; i <= r; ++i)
        tmp.pb(i);
    return Query(tmp) < tmp.size();
}
void binsearch(int x, int l, int r){
    if(l == r){
        pos[x].pb(l);
        return;
    }
    if(okay(x, l, (l+r)/2))
        binsearch(x, l, (l+r)/2);
    if(okay(x, (l+r)/2+1, r))
        binsearch(x, (l+r)/2+1, r);
}

int quad(int x){
    for(auto u : pos[x])
        if(pos[u].size() == 1) return u;
    if(Query({x, pos[x][0]}) == 1)
        return pos[x][0];
    else
        return pos[x][1];
}
void Solve(int n){
    for(int i = 1; i <= n; ++i)
        binsearch(i, n+1, 2*n);
    for(int i = n+1; i <= 2*n; ++i)
        binsearch(i, 1, n);
    for(int i = 1; i <= 2*n; ++i){
        if(ans[i]) continue;
        int okay[2] = {0, 0};
        for(int j = 0; j < 2; ++j){
            if(j >= pos[i].size() || ans[pos[i][j]]) continue;
            for(auto u : pos[pos[i][j]])
                if(u == i)
                    okay[j] = 1;
        }
        if(okay[0] && !okay[1]){
            ans[i] = pos[i][0];
            ans[pos[i][0]] = i;
        }
        else if(okay[1] && !okay[0]){
            ans[i] = pos[i][1];
            ans[pos[i][1]] = i;
        }
        else{   
            int k = quad(i);
            ans[i] = k;
            ans[k] = i;
        }
    }
    for(int i = 1; i <= n; ++i)
        Answer(i, ans[i]);
}

Compilation message

chameleon.cpp: In function 'int okay(int, int, int)':
chameleon.cpp:22:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     return Query(tmp) < tmp.size();
            ~~~~~~~~~~~^~~~~~~~~~~~
chameleon.cpp: In function 'void Solve(int)':
chameleon.cpp:52:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(j >= pos[i].size() || ans[pos[i][j]]) continue;
                ~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Incorrect 40 ms 384 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 4 ms 384 KB Wrong Answer [6]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 4 ms 384 KB Wrong Answer [6]
3 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Incorrect 5 ms 384 KB Wrong Answer [6]
3 Halted 0 ms 0 KB -

Subtask #5
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Incorrect 40 ms 384 KB Wrong Answer [3]
4 Halted 0 ms 0 KB -