oj.uz

답안 #926570

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
926570 2024-02-13T10:18:15 Z hotboy2703 최후의 만찬 (IOI12_supper) C++14
0 / 100
 162 ms 28500 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
#define MP make_pair
const ll MAXN = 1e5;
#include "assistant.h"
#include "advisor.h"

namespace {
    namespace penis{
        ll c[MAXN+100];
        vector <ll> pos[MAXN+100];
        vector <ll> event[MAXN+100];
        ll n,k;
        void advisor(){
            set <pll> s;
            for (ll i = n-1;i >= 0;i--){
                pos[i].push_back(n+1);
            }
            for (ll i = n-1;i >= 0;i--){
                pos[c[i]].push_back(i);
            }
            for (ll i = 0;i < k;i ++){s.insert(MP(pos[i].back(),i));event[i].push_back(-1);}
            for (ll i = 0;i < n;i ++){
                if (s.insert(MP(i,c[i])).se){
                    event[c[i]].push_back(i);
                    pll tmp = *s.rbegin();
                    s.erase(s.find(tmp));
                    event[tmp.se].push_back(i);
                }
                s.erase(MP(i,c[i]));
                pos[c[i]].pop_back();
                s.insert(MP(pos[c[i]].back(),c[i]));
            }
            for (ll i = 0;i < n;i ++)pos[i].clear();
            for (ll i = 0;i < n;i ++)pos[c[i]].push_back(i);
            auto cnt = [&](ll color,ll l,ll r){
                return upper_bound(pos[color].begin(),pos[color].end(),r)-lower_bound(pos[color].begin(),pos[color].end(),l);
            };
            vector <pll> all_event;
            for (ll i = 0;i < n;i ++){
                if (sz(event[i])%2==1)event[i].push_back(n+1);
                for (ll j = 0;j < sz(event[i]);j += 2){
                    all_event.push_back(MP(event[i][j] == -1 ? i - k : event[i][j],cnt(i,event[i][j]+1,event[i][j+1])));
                }
            }
            sort(all_event.begin(),all_event.end());
            for (auto x:all_event){
                while (x.se--){
                    WriteAdvice(1);
                }
                WriteAdvice(0);
            }
        }
    }
    namespace pussy{
        ll hint[MAXN*2+100];
        ll n,k;
        ll ptr;
        ll life[MAXN*2+100];
        bool in_s[MAXN+100];
        ll get_hint(){
            ll cnt = 0;
            while (hint[ptr]==1)ptr++,cnt++;
            ptr++;
//            cout<<"GET "<<cnt<<endl;
            return cnt;
        }
        void assistant(){
            set <pll> s;
            for (ll i = 0;i < k;i ++){life[i] = get_hint();s.insert({life[i],i});in_s[i] = 1;}
            for (ll i = 0;i < n;i ++){
                ll x = GetRequest();
                if (in_s[x]){
                    life[x]--;
                }
                else{
                    pll tmp = *s.begin();
                    in_s[tmp.se]=0;
                    PutBack(tmp.se);
                    s.erase(tmp);
                    life[x] = get_hint();
                    s.insert({life[x],x});
                    in_s[x] = 1;
                }
            }
        }
    }
}



void ComputeAdvice(int *C, int N, int K, int M) {
    using namespace penis;
    for (ll i = 0;i < N;i ++){c[i] = C[i];}
    n=N;
    k=K;
    penis::advisor();
}


#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
#define pll pair <ll,ll>
#define fi first
#define se second
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1LL)
#define MASK(i) (1LL << (i))
#define MP make_pair
const ll MAXN = 1e5;
#include "assistant.h"
#include "advisor.h"

namespace {
    namespace penis{
        ll c[MAXN+100];
        vector <ll> pos[MAXN+100];
        vector <ll> event[MAXN+100];
        ll n,k;
        void advisor(){
            set <pll> s;
            for (ll i = n-1;i >= 0;i--){
                pos[i].push_back(n+1);
            }
            for (ll i = n-1;i >= 0;i--){
                pos[c[i]].push_back(i);
            }
            for (ll i = 0;i < k;i ++){s.insert(MP(pos[i].back(),i));event[i].push_back(-1);}
            for (ll i = 0;i < n;i ++){
                if (s.insert(MP(i,c[i])).se){
                    event[c[i]].push_back(i);
                    pll tmp = *s.rbegin();
                    s.erase(s.find(tmp));
                    event[tmp.se].push_back(i);
                }
                s.erase(MP(i,c[i]));
                pos[c[i]].pop_back();
                s.insert(MP(pos[c[i]].back(),c[i]));
            }
            for (ll i = 0;i < n;i ++)pos[i].clear();
            for (ll i = 0;i < n;i ++)pos[c[i]].push_back(i);
            auto cnt = [&](ll color,ll l,ll r){
                return upper_bound(pos[color].begin(),pos[color].end(),r)-lower_bound(pos[color].begin(),pos[color].end(),l);
            };
            vector <pll> all_event;
            for (ll i = 0;i < n;i ++){
                if (sz(event[i])%2==1)event[i].push_back(n+1);
                for (ll j = 0;j < sz(event[i]);j += 2){
                    all_event.push_back(MP(event[i][j] == -1 ? i - k : event[i][j],cnt(i,event[i][j]+1,event[i][j+1])));
                }
            }
            sort(all_event.begin(),all_event.end());
            for (auto x:all_event){
                while (x.se--){
                    WriteAdvice(1);
                }
                WriteAdvice(0);
            }
        }
    }
    namespace pussy{
        ll hint[MAXN*2+100];
        ll n,k;
        ll ptr;
        ll life[MAXN*2+100];
        bool in_s[MAXN+100];
        ll get_hint(){
            ll cnt = 0;
            while (hint[ptr]==1)ptr++,cnt++;
            ptr++;
//            cout<<"GET "<<cnt<<endl;
            return cnt;
        }
        void assistant(){
            set <pll> s;
            for (ll i = 0;i < k;i ++){life[i] = get_hint();s.insert({life[i],i});in_s[i] = 1;}
            for (ll i = 0;i < n;i ++){
                ll x = GetRequest();
                if (in_s[x]){
                    life[x]--;
                }
                else{
                    pll tmp = *s.begin();
                    in_s[tmp.se]=0;
                    PutBack(tmp.se);
                    s.erase(tmp);
                    life[x] = get_hint();
                    s.insert({life[x],x});
                    in_s[x] = 1;
                }
            }
        }
    }
}


void Assist(unsigned char *A, int N, int K, int R) {
    using namespace pussy;
    for (ll i = 0;i < R;i ++)hint[i]=A[i];
    n=N,k=K;
    pussy::assistant();

}

Compilation message

advisor.cpp:77:14: warning: 'void {anonymous}::pussy::assistant()' defined but not used [-Wunused-function]
   77 |         void assistant(){
      |              ^~~~~~~~~

assistant.cpp:23:14: warning: 'void {anonymous}::penis::advisor()' defined but not used [-Wunused-function]
   23 |         void advisor(){
      |              ^~~~~~~

Subtask #1
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 13072 KB Output is correct
2 Incorrect 3 ms 13084 KB Output isn't correct - not an optimal way
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 12 ms 14704 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 106 ms 24280 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #4
0 / 35.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 13884 KB Output isn't correct - not an optimal way
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 39.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 149 ms 26776 KB Output isn't correct - not an optimal way
2 Incorrect 117 ms 26896 KB Output isn't correct - not an optimal way
3 Incorrect 145 ms 27540 KB Output isn't correct - not an optimal way
4 Incorrect 119 ms 27272 KB Output isn't correct - not an optimal way
5 Incorrect 122 ms 26992 KB Output isn't correct - not an optimal way
6 Incorrect 162 ms 27604 KB Output isn't correct - not an optimal way
7 Incorrect 129 ms 27012 KB Output isn't correct - not an optimal way
8 Incorrect 125 ms 27108 KB Output isn't correct - not an optimal way
9 Incorrect 137 ms 27256 KB Output isn't correct - not an optimal way
10 Correct 110 ms 28500 KB Output is correct - 125000 bits used