oj.uz

Submission #728359

# Submission time Handle Problem Language Result Execution time Memory
728359 2023-04-22T09:58:28 Z YassineBenYounes Rarest Insects (IOI22_insects) C++17
99.95 / 100
 59 ms 492 KB 
#include<bits/stdc++.h>
 
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef double db;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define pbds tree<pair<ll, ll>, null_type, less<pair<ll,ll>>,rb_tree_tag, tree_order_statistics_node_update>
using namespace __gnu_pbds;
ll gcd(ll a , ll b) {return b ? gcd(b , a % b) : a ;} // greatest common divisor (PGCD)
ll lcm(ll a , ll b) {return (a * b) / gcd(a , b);} // least common multiple (PPCM)
int dx[8] = {1, 0, 0, -1, 1, 1, -1, -1};
int dy[8] = {0, 1, -1, 0, 1, -1, -1, 1};
#define endl "\n"
#define ss second
#define ff first
#define all(x) (x).begin() , (x).end()
#define pb push_back
#define vi vector<int>
#define vii vector<pair<int,int>>
#define vl vector<ll>
#define vll vector<pair<ll,ll>>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd  pair<double,double>
#define vdd  vector<pdd>
#define speed ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
////////////////////Only Clear Code//////////////////////////
 
void usaco_problem(){
    freopen("milkvisits.in", "r", stdin);
    freopen("milkvisits.out", "w", stdout);
}
 
void init(){
    #ifndef ONLINE_JUDGE
 
freopen("input.txt", "r", stdin);
 
freopen("output.txt", "w", stdout);
 
#endif // ONLINE_JUDGE
}
 
const int mx = 2005;
const int LOG = 25;
const int inf = 1e9;
const ll mod = 1e8;
map<int, int> mp;
 
ll bs = 0;
 
vi arr[mx];
int color[mx];
bool vis[mx];
 
void move_inside(int i);

void move_outside(int i);

int press_button();
    
int min_cardinality(int n){
    int c = 1;
    for(int i = 0; i < n;i++){
        move_inside(i);
        int v = press_button();
        if(v==1){
            color[i] = c;
            arr[c].pb(i);
            c++;
        }
        if(v == 2){
            move_outside(i);
        }
    }
    if(c <= bs){
        for(int i = 0; i < n;i++){
            if(color[i] != 0){
                move_outside(i);
            }
        }
        for(int i = 1; i < c;i++){
            for(int x : arr[i]){
                move_inside(x);
                vis[x] = 1;
            }
            for(auto x : mp){
                cout << x.ff << " " << x.ss << endl;
            }
            cout << endl;
            int st = 2;
            for(int j = 0;j < n;j++){
                if(vis[j])continue;
                move_inside(j);
                int v = press_button();
                if(v == st){
                    color[j] = i;
                    vis[j] = 1;
                    st++;
                    arr[i].pb(j);
                }
                else{
                    move_outside(j);
                }
            }
            for(int x : arr[i]){
                move_outside(x);
            }
        }
        int ans = 1e9;
        for(int i = 1; i < c;i++){
            int s = arr[i].size();
            ans = min(ans, s);
        }
        return ans;
    }
    for(int i = 0; i < n;i++){
        if(color[i] != 0){
            vis[i] = 1;
        }
    }
    int l = 1, r = n/(c-1);
    int ans = 0;
    vi ve;
    vi no(n+5);
    while(l <= r){
        int md = (l+r)/2;
        int x = (c-1) + ve.size();
        vi nw;
        vi temp(n+5);
        int sup = md * (c-1);
        for(int i = 0; i < n && x < sup;i++){
            if(vis[i] || no[i])continue;
            move_inside(i);
            int v = press_button();
            if(v <= md){
                x++;
                ve.pb(i);
                nw.pb(i);
                vis[i]= 1;
            }
            else{
                temp[i] = 1;
                move_outside(i);
            }
        }
        if(x < sup){
            r = md-1;
            for(int x : nw){
                ve.erase(find(all(ve), x));
                move_outside(x);
                vis[x] = 0;
            }
            for(int i = 0; i < n;i++){
                no[i] |= temp[i];
            }
        }
        else{
            ans = md;
            l = md+1;
        }
    }
    return ans;
}
/*
void run_case(){
    int n;cin >> n;
    for(int i = 0; i < n;i++){
        cin >> sol[i];
    }
    cout << min_cardinality(n) << endl;
}
 
int main(){
    init();
    speed;
    int t;
    //cin >> t;
    t = 1;
    while(t--){
        run_case();
    }
}*/
 
/*
    NEVER GIVE UP!
    DOING SMTHNG IS BETTER THAN DOING NTHNG!!!
    Your Guide when stuck:
    - Continue keyword only after reading the whole input
    - Don't use memset with testcases
    - Check for corner cases(n=1, n=0)
    - Check where you declare n(Be careful of declaring it globally and in main)
*/

Compilation message

insects.cpp: In function 'void usaco_problem()':
insects.cpp:33:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     freopen("milkvisits.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
insects.cpp:34:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     freopen("milkvisits.out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
insects.cpp: In function 'void init()':
insects.cpp:40:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 | freopen("input.txt", "r", stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
insects.cpp:42:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 | freopen("output.txt", "w", stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 4 ms 336 KB Output is correct
7 Correct 3 ms 336 KB Output is correct
8 Correct 3 ms 336 KB Output is correct
9 Correct 5 ms 336 KB Output is correct
10 Correct 5 ms 336 KB Output is correct
11 Correct 3 ms 336 KB Output is correct
12 Correct 4 ms 352 KB Output is correct
13 Correct 5 ms 336 KB Output is correct
14 Correct 4 ms 336 KB Output is correct
15 Correct 4 ms 336 KB Output is correct
16 Correct 6 ms 336 KB Output is correct
17 Correct 5 ms 360 KB Output is correct
18 Correct 3 ms 336 KB Output is correct
19 Correct 5 ms 336 KB Output is correct
20 Correct 2 ms 356 KB Output is correct
21 Correct 4 ms 336 KB Output is correct
22 Correct 2 ms 336 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 4 ms 336 KB Output is correct
7 Correct 3 ms 336 KB Output is correct
8 Correct 3 ms 336 KB Output is correct
9 Correct 5 ms 336 KB Output is correct
10 Correct 5 ms 336 KB Output is correct
11 Correct 3 ms 336 KB Output is correct
12 Correct 4 ms 352 KB Output is correct
13 Correct 5 ms 336 KB Output is correct
14 Correct 4 ms 336 KB Output is correct
15 Correct 4 ms 336 KB Output is correct
16 Correct 6 ms 336 KB Output is correct
17 Correct 5 ms 360 KB Output is correct
18 Correct 3 ms 336 KB Output is correct
19 Correct 5 ms 336 KB Output is correct
20 Correct 2 ms 356 KB Output is correct
21 Correct 4 ms 336 KB Output is correct
22 Correct 2 ms 336 KB Output is correct
23 Correct 20 ms 348 KB Output is correct
24 Correct 5 ms 372 KB Output is correct
25 Correct 15 ms 352 KB Output is correct
26 Correct 20 ms 336 KB Output is correct
27 Correct 24 ms 352 KB Output is correct
28 Correct 8 ms 364 KB Output is correct
29 Correct 26 ms 340 KB Output is correct
30 Correct 22 ms 348 KB Output is correct
31 Correct 21 ms 456 KB Output is correct
32 Correct 28 ms 340 KB Output is correct
33 Correct 15 ms 356 KB Output is correct
34 Correct 27 ms 344 KB Output is correct
35 Correct 25 ms 340 KB Output is correct
36 Correct 26 ms 336 KB Output is correct
37 Correct 21 ms 348 KB Output is correct
38 Correct 27 ms 336 KB Output is correct
39 Correct 24 ms 360 KB Output is correct
40 Correct 15 ms 364 KB Output is correct
41 Correct 8 ms 336 KB Output is correct

Subtask #3
74.95 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 30 ms 340 KB Output is correct
8 Correct 20 ms 368 KB Output is correct
9 Correct 24 ms 476 KB Output is correct
10 Correct 56 ms 336 KB Output is correct
11 Correct 33 ms 344 KB Output is correct
12 Correct 27 ms 336 KB Output is correct
13 Correct 45 ms 456 KB Output is correct
14 Correct 53 ms 336 KB Output is correct
15 Correct 41 ms 368 KB Output is correct
16 Correct 37 ms 364 KB Output is correct
17 Correct 44 ms 340 KB Output is correct
18 Correct 47 ms 336 KB Output is correct
19 Correct 38 ms 344 KB Output is correct
20 Correct 43 ms 336 KB Output is correct
21 Correct 48 ms 492 KB Output is correct
22 Correct 46 ms 340 KB Output is correct
23 Correct 44 ms 336 KB Output is correct
24 Correct 31 ms 348 KB Output is correct
25 Correct 27 ms 364 KB Output is correct
26 Correct 19 ms 336 KB Output is correct
27 Correct 41 ms 348 KB Output is correct
28 Correct 36 ms 336 KB Output is correct
29 Correct 45 ms 488 KB Output is correct
30 Correct 48 ms 336 KB Output is correct
31 Correct 45 ms 340 KB Output is correct
32 Correct 48 ms 364 KB Output is correct
33 Correct 45 ms 348 KB Output is correct
34 Correct 38 ms 352 KB Output is correct
35 Partially correct 54 ms 340 KB Output is partially correct
36 Correct 33 ms 348 KB Output is correct
37 Correct 47 ms 336 KB Output is correct
38 Correct 59 ms 344 KB Output is correct
39 Correct 42 ms 336 KB Output is correct
40 Correct 28 ms 340 KB Output is correct
41 Correct 40 ms 336 KB Output is correct
42 Partially correct 39 ms 364 KB Output is partially correct
43 Correct 11 ms 464 KB Output is correct
44 Correct 41 ms 336 KB Output is correct
45 Correct 33 ms 356 KB Output is correct
46 Correct 22 ms 344 KB Output is correct
47 Correct 25 ms 464 KB Output is correct
48 Correct 19 ms 384 KB Output is correct