Submission #373619

#	Time	Username	Problem	Language	Result	Execution time	Memory
373619		teehandsome	Horses (IOI15_horses)	C++11	17 / 100	1591 ms	9424 KiB

horses

#include "horses.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define endl '\n'
#define INF 1e9+7
#define all(x) x.begin(),x.end()

using namespace std;
using namespace __gnu_pbds;
using pii=pair<int,int>;
using ppi=pair<int,pii>;
using ll=long long;
using oset=tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>;

void _print(vector<pii> x) {cerr<<"["; for(auto e:x) cerr<<"{"<<e.first<<","<<e.second<<"} ,"; cerr<<"]";}
template<typename T>
void _print(vector<T> x) {cerr<<"{"; for(auto e:x) cerr<<e<<","; cerr<<"}";}
void _print(pii x) {cerr<<"{"<<x.first<<","<<x.second<<"}";}
template<typename T>
void _print(T x) {cerr<<x;}
void dbg() {cerr<<endl;}
template<typename Head,typename... Tail>
void dbg(Head H,Tail... T) {
    _print(H);
    if(sizeof...(T)) cerr<<",";
    else cerr<<"]";
    dbg(T...);
}
#define debug(...) cerr<<"[\""<<#__VA_ARGS__<<"\"]: [",dbg(__VA_ARGS__);

vector<int> x,y;
int n;

const int md=INF;

string add(string a,string b) {
    int tod=0;
    string res;
    if(a.size()<b.size()) swap(a,b);
    int len=a.size();
    reverse(all(a)); reverse(all(b));
    while(b.size()<len) b.push_back('0');
    for(int i=0;i<len;i++) {
        int temp=a[i]+b[i]-'0'-'0'+tod;
        int len=temp%10;
        res.push_back(len+'0');
        tod=temp/10;
    }
    if(tod) res.push_back(tod+'0');
    reverse(all(res));
    return res;
}
string mul(string a,string b) {
    string res="0";
    if(a.size()<b.size()) swap(a,b);
    int len=a.size();
    int lenB=b.size();
    reverse(all(a)); reverse(all(b));
//    while(b.size()<len) b.push_back('0');
    for(int i=0;i<len;i++) {
        for(int j=0;j<lenB;j++) {
           int temp=(a[i]-'0')*(b[j]-'0'); if(!temp) continue;
           string temp2=to_string(temp);
           for(int cnt=0;cnt<i+j;cnt++) temp2.push_back('0');
//           debug(temp2);
//           debug(res,temp2);
           res=add(res,temp2);
//           debug(res);
        }
    }
    return res;
}
string max2(string a,string b) {
    if(a.size()>b.size()) return a;
    if(a.size()<b.size()) return b;
    int len=a.size();
    for(int i=0;i<len;i++) {
        if(a[i]>b[i]) return a;
        if(a[i]<b[i]) return b;
    }
    return a;
}
string lop(string a,string b) {
    int lenA=a.size(),lenB=b.size();
    reverse(all(a)); reverse(all(b));
    string res="";
    for(int i=0;i<lenB;i++) {
        if(a[i]>=b[i]) {
            res.push_back(a[i]-b[i]+'0');
        }
        else {
            res.push_back(a[i]+10-b[i]+'0');
            a[i+1]--;
        }
    }
    for(int i=lenB;i<lenA;i++) res.push_back(a[i]);
    reverse(all(res));
    return res;
}
int modulo(string a,string b) {
    while(max2(a,b)==a) a=lop(a,b);
    return stoi(a);
}
int solve() {
    string mx="0";
    string cur="1";
    for(int i=0;i<n;i++) {
        cur=mul(cur,to_string(x[i]));
        mx=max2(mx,mul(cur,to_string(y[i])));
    }
    return modulo(mx,to_string(md));
}

int init(int N, int X[], int Y[]) {
//    debug(lop("123123","990"));
    n=N;
    for(int i=0;i<N;i++) {
        x.push_back(X[i]); y.push_back(Y[i]);
    }
    return solve();
}

int updateX(int pos, int val) {
	x[pos]=val;
	return solve();
}

int updateY(int pos, int val) {
	y[pos]=val;
	return solve();
}

Compilation message (stderr)

horses.cpp: In function 'std::string add(std::string, std::string)':
horses.cpp:42:19: warning: conversion from 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   42 |     int len=a.size();
      |             ~~~~~~^~
horses.cpp:44:19: warning: comparison of integer expressions of different signedness: 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   44 |     while(b.size()<len) b.push_back('0');
      |           ~~~~~~~~^~~~
horses.cpp:47:13: warning: declaration of 'len' shadows a previous local [-Wshadow]
   47 |         int len=temp%10;
      |             ^~~
horses.cpp:42:9: note: shadowed declaration is here
   42 |     int len=a.size();
      |         ^~~
horses.cpp:48:26: warning: conversion from 'int' to 'char' may change value [-Wconversion]
   48 |         res.push_back(len+'0');
      |                       ~~~^~~~
horses.cpp:51:30: warning: conversion from 'int' to 'char' may change value [-Wconversion]
   51 |     if(tod) res.push_back(tod+'0');
      |                           ~~~^~~~
horses.cpp: In function 'std::string mul(std::string, std::string)':
horses.cpp:58:19: warning: conversion from 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   58 |     int len=a.size();
      |             ~~~~~~^~
horses.cpp:59:20: warning: conversion from 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   59 |     int lenB=b.size();
      |              ~~~~~~^~
horses.cpp: In function 'std::string max2(std::string, std::string)':
horses.cpp:78:19: warning: conversion from 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   78 |     int len=a.size();
      |             ~~~~~~^~
horses.cpp: In function 'std::string lop(std::string, std::string)':
horses.cpp:86:20: warning: conversion from 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   86 |     int lenA=a.size(),lenB=b.size();
      |              ~~~~~~^~
horses.cpp:86:34: warning: conversion from 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} to 'int' may change value [-Wconversion]
   86 |     int lenA=a.size(),lenB=b.size();
      |                            ~~~~~~^~
horses.cpp:91:36: warning: conversion from 'int' to 'char' may change value [-Wconversion]
   91 |             res.push_back(a[i]-b[i]+'0');
horses.cpp:94:39: warning: conversion from 'int' to 'char' may change value [-Wconversion]
   94 |             res.push_back(a[i]+10-b[i]+'0');

• Subtask 1: 17 / 17
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 23
• Subtask 5: 0 / 23