oj.uz

Submission #881012

# Submission time Handle Problem Language Result Execution time Memory
881012 2023-11-30T10:46:45 Z alicanyaz Carnival Tickets (IOI20_tickets) C++14
16 / 100
 381 ms 62368 KB 
#pragma GCC optimize("Ofast","unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ost;
#define endl "\n"
#define ll long long
#define ull unsigned long long
#define ld long double
#define pi pair<int,int> 
#define pll pair<long long,long long>
#define vi vector<int>
#define vll vector<long long>
#define vpi vector<pair<int,int>>
#define vpll vector<pair<long long,long long>>
#define vvi vector<vector<int>>
#define vvll vector<vector<long long>>
#define vr vector<range<int>>
#define cd complex<double>
#define pb push_back
template<typename T>
struct matrix{
    vector<T> mtx;
    T Tdef;
    int column=-1,row=-1;
    matrix()  {}
    matrix(int r,int c) {
        mtx.assign(r*c,Tdef);
        row = r;
        column = c;
    }
    matrix(int r,int c,T val){
        mtx.assign(r*c,val);
        row = r;
        column = c;
    }
    struct proxy{
        matrix *m ;
        int i;
        proxy(matrix* x , int y) : m(x) , i(y){}
        T &operator[] (int j){
            return (m->mtx[i*(m->row) + j]);
        }
    };
    proxy operator[](int i){
        return proxy(this,i);
    }
    void fill(T x){for(auto &y:mtx)y=x;}
    void fill_row(int rw,T x,int l=0,int r=-1){
        if(r==-1)r = column-1;
        for(int i=l;i<=r;i++){
            mtx[rw*row + i] = x;
        }
    }
    void fill_column(int cl,T x,int l=0,int r=-1){
        if(r == -1)r = row-1;
        for(int i=l;i<=r;i++){
            mtx[i*row + cl] = x;
        }
    }
    void inc_row(int rw,T x,int l=0,int r=-1){
        if(r==-1)r = column-1;
        for(int i=l;i<=r;i++){
            mtx[rw*row + i] += x;
        }
    }
    void inc_column(int cl,T x,int l=0,int r=-1){
        if(r == -1)r = row-1;
        for(int i=l;i<=r;i++){
            mtx[i*row + cl] +=x;
        }
    }
    int count(int rw,T x,int l=0,int r=-1){
        if(r == -1)r = column-1;
        int cnt = 0;
        for(int i=l;i<=r;i++)cnt += (mtx[rw*row + i] == x);
        return cnt;
    }
    
};
template<typename V,typename S> istream& operator >> (istream &x,pair<V,S> &p){cin >> p.first >> p.second ;return x;}
template<typename V,typename S> ostream& operator << (ostream &x,const pair<V,S> &p){cout << p.first <<" "<<p.second;return x;}
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define abs(x) ((x)>0?(x):-((x)))
#define fr(i,j) for(int i=0;i<j;i++)
#define frt(a,b,c) for(int a=b;a<c;a++)
#define fra(x,y) for(auto &x:y)
#define min(a,b) ((a)<(b)?(a):(b))
#define all(x) x.begin(),x.end()
int mlog(int x) {
    return 32 - __builtin_clz(x) - 1;
}
ll sum(ll a,ll b,ll M=1e+9+7){
    a%=M;b%=M;return (a+b)%M;
}
ll subs(ll a,ll b,ll M=1e+9+7){
    a-=b;a%=M;if(a<0)a+=M;return a;
}
ll mult(ll a,ll b,ll M=1e+9+7){
    a%=M;b%=M;return (a*b)%M;
}
ll bp(ll a,ll b,ll M=1e+9+7){
    if(b == 0)return 1;
    if(b == 1)return a;
    ll x = bp(a,b/2,M);
    x = mult(x,x,M);
    if(b%2)x=mult(x,a,M);
    return x;
}
#include "tickets.h"
void allocate_tickets_dbg(vvi a){
    fra(x,a){fra(y,x)cout<<y<<" ";cout<<endl;}
}
ll find_maximum(int k,vvi x){
    int n = x.size();
    int m = x[0].size();
    ll ans = 0;
    vpi points(n,{k-1,m-1}); // maximum of minimum : p.first     maximum of maximum : p.second
    vvi isactive(n,vi(m,-1));
    fr(i,n)
        fr(j,k){isactive[i][j] =j;ans -= x[i][j];}
    priority_queue<pair<ll,int>> sst;
    //set<pair<ll,int>,greater<pair<ll,int>>> sst;
    
    fr(i,n)sst.push({x[i][points[i].first] + x[i][points[i].second],i});
    for(int turn=0;turn<(n*k)/2;turn++){
        auto it = sst.top();
        ans += it.first;
        isactive[it.second][points[it.second].second]=isactive[it.second][points[it.second].first];
        isactive[it.second][points[it.second].first]=-1;
        points[it.second].first--;points[it.second].second--;
        sst.pop();
        if(points[it.second].first < 0)continue;
        sst.push({x[it.second][points[it.second].first] + x[it.second][points[it.second].second],it.second});
    }
    allocate_tickets(isactive);
    return ans;
}
 
 
 
/*
int32_t main(){
    fastio;
    cout << find_maximum(3,{{0,1,1,1},{0,1,1,1},{0,1,1,1},{0,0,0,1}});
}*/

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB There is no ticket of color 1 on day 0
2 Halted 0 ms 0 KB -

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 432 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 16 ms 3164 KB Output is correct
6 Correct 381 ms 62368 KB Output is correct

Subtask #3
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Contestant returned 2 but the tickets gives a total value of 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB There is no ticket of color 1 on day 2
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB There is no ticket of color 1 on day 2
2 Halted 0 ms 0 KB -

Subtask #6
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB There is no ticket of color 1 on day 2
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB There is no ticket of color 1 on day 0
2 Halted 0 ms 0 KB -