OJ Board

Code: Select all

#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cctype>
#include <utility>

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
#define REP(i,n) for(int _n=n, i=0;i<_n;++i)
#define FOR(i,a,b) for(int i=(a),_b=(b);i<_b;++i)
#define sz(v) ((int)(v).size())
#define pb push_back
#define FORSZ(i,a,v) FOR(i,a,sz(v))
#define REPSZ(i,v) FORSZ(i,0,v)

inline int maxflow(VVI &matrix, int src, int dest){
	int cap[sz(matrix)];
	int in[sz(matrix)];
	int previous[sz(matrix)];
	int total = 0;
	while(true){
		int last = dest;
		memset(cap, 0, sizeof(cap));
		memset(in, 0, sizeof(in));
		queue<int> Q;
		Q.push(src);
		cap[src] = 999999;
		int done = 0, node;
		while(sz(Q) > 0){
			node = Q.front();
			Q.pop();
			if(node == dest){ done = 1; break;}
			else{
				FOR(i, 0, sz(matrix[node])){
					int obj = matrix[node][i];
					if(cap[i] < min(cap[node], obj)){
						cap[i] = min(cap[node], obj);
						previous[i] = node;
						if(in[i] == 0){
							Q.push(i);
							in[i] = 1;
							if(node == 1) break;
							//Only one at a time, if monkey A can't drink, we ahven't to test whit monkey A+1
						}
					}
				}
			}
		}
		if(done){
			total += cap[0];
			while(last != src){
				matrix[last][previous[last]] += cap[0];
				matrix[previous[last]][last] -= cap[0];
				last = previous[last];
			}
		}else break;
	}
	return total;
}


int main(){
	int monkeys, fonts, cases = 1;
	while(cin >> monkeys){
		if(monkeys == 0) return 0;
		cin >> fonts;
		int need[monkeys];
		int start[monkeys];
		int end[monkeys];
		int total = 0, minim = 9999999, maxim = 0;
		FOR(i, 0 , monkeys){
			cin >> need[i] >> start[i] >> end[i];
			total += need[i];
			if(start[i] < minim) minim = start[i];
			if(maxim < end[i]) maxim = end[i];
		}
		
		//Only making sure it's water for them all
		if(total > (maxim - minim) * fonts){
			cout << "Case " << cases << ": No" <<endl;
			cases++;
			continue;
		}
		//Signaling where to break the interval
		vector<int> placesToBreak(2*monkeys);
		FOR(i,0,monkeys){
			placesToBreak[i] = start[i];
			placesToBreak[monkeys+i] = end[i];
		}
		sort(placesToBreak.begin(), placesToBreak.end());
		
		int intervalFirst[monkeys + 2 + sz(placesToBreak)];
		int intervalLast[monkeys + 2 + sz(placesToBreak)];
		int firstEmpty = monkeys + 2;
		intervalFirst[firstEmpty] = placesToBreak[0];
		FOR(i, 1, 2*monkeys){
			if( placesToBreak[i] != placesToBreak[i-1]){
				intervalLast[firstEmpty] = placesToBreak[i];
				firstEmpty++;
				intervalFirst[firstEmpty] = placesToBreak[i];
			}
		}
		//Breaks saved
		
		//Creating the matrix and placing capacities
		//From monkey to interval
		//From interval to water
		//From source to monkeys (their thirstyness?)
		VVI matrix(firstEmpty, VI(firstEmpty,0));
		FOR(i, 0, monkeys)
			FOR(j, monkeys+1, firstEmpty)
				if(start[i] <= intervalFirst[j] && end[i] > intervalFirst[j])
					matrix[i+2][j] = intervalLast[j] - intervalFirst[j];
		FOR(i,monkeys+2,firstEmpty) matrix[i][0] = (intervalLast[i]-intervalFirst[i])*fonts;
		FOR(i,0,monkeys) matrix[1][i+2] = need[i];
		
		//Calling the maxflow
		int bo = maxflow(matrix, 1, 0);
		
		if(bo != total) cout << "Case " << cases << ": No" <<endl;
		else{
			cout << "Case " << cases << ": Yes" << endl;
			VI toPrint;
			int firstToUse[sz(matrix)];
			
			FOR(j, monkeys+2, sz(matrix)){
				firstToUse[j] = intervalFirst[j];
			}
			FOR(i, 0, monkeys){
				toPrint.clear();
				FOR(j, monkeys+2, sz(matrix)){
					int aux = intervalLast[j] - intervalFirst[j];
					if(start[i] <= intervalFirst[j] && end[i] > intervalFirst[j] && matrix[i+2][j] < aux){
						int sobren = firstToUse[j] - intervalFirst[j] - matrix[i+2][j];
						if( sobren <= 0 ){
							//See if one interval follows the last
							if(toPrint.size() == 0 || toPrint[sz(toPrint)-1] != firstToUse[j]){
								toPrint.pb(firstToUse[j]);
								toPrint.pb(firstToUse[j] + (intervalLast[j]-intervalFirst[j]) - matrix[i+2][j]);
								firstToUse[j] = toPrint[sz(toPrint)-1];
								if(firstToUse[j] == intervalLast[j]){firstToUse[j] = intervalFirst[j];}
							}else{
								//Puting this interval with the last
								toPrint[sz(toPrint)-1] = firstToUse[j] + (intervalLast[j]-intervalFirst[j]) - matrix[i+2][j];
								firstToUse[j] = toPrint[sz(toPrint)-1];
								if(firstToUse[j] == intervalLast[j]){firstToUse[j] = intervalFirst[j];}
							}
						}
						else{
							
							if(sz(toPrint)==0 || toPrint[sz(toPrint)-1]!=intervalFirst[j]){
								toPrint.pb(intervalFirst[j]);
								toPrint.pb(intervalFirst[j] + sobren);
								toPrint.pb(firstToUse[j]);
								toPrint.pb(intervalLast[j]);
								firstToUse[j] = toPrint[sz(toPrint)-3];
								if(firstToUse[j] == intervalLast[j]){firstToUse[j] = intervalFirst[j];}
							}else{
								//Puting this interval with the last
								toPrint[sz(toPrint)-1] = intervalFirst[j] + sobren;
								toPrint.pb(firstToUse[j]);
								toPrint.pb(intervalLast[j]);
								firstToUse[j] = toPrint[sz(toPrint)-3];
								if(firstToUse[j] == intervalLast[j]){firstToUse[j] = intervalFirst[j];}
							}
						}
					}
				}
				cout << sz(toPrint)/2;
				FOR(a,0,sz(toPrint)){
					cout << " ("<<toPrint[a]<<","<<toPrint[a+1]<<")";
					a++;
				}cout<<endl;
			}
		}
		cases++;
	}
}

Code: Select all

Code: Select all

/* Lazy Correct Program */
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>

typedef struct {
   int v, a, b;
} Monkey;
#define MAX_MONKEY 128
static Monkey mon[MAX_MONKEY];

int main()
{
   FILE *in, *out;

   in = fopen("in", "r");
   out = fopen("out", "r");


   int N, M, i, j, caseno = 1;
   char buf[64];
   while (fscanf(in, "%d", &N) && N) {
      fscanf(in, "%d", &M);
      for (i = 0; i < N; ++i)
         fscanf(in, "%d %d %d", &mon[i].v, &mon[i].a, &mon[i].b);

      printf("Case %d:\n", caseno++);
      fflush(stdout);

      fgets(buf, sizeof(buf), out);
      if (buf[strlen(buf)-2] == 'o') {
         printf("You answered \"No\". I can't verify.\n");
      } else {
         int *count = (int*)calloc(sizeof(int), 1024);
         for (i = 0; i < N; ++i) {
            int k, v;
            fscanf(out, "%d", &k);
            v = 0;
            int tmp = mon[i].a - 1;
            while ( k-- ) {
               int a, b;
               fscanf(out, " (%d,%d)", &a, &b);
               assert(a < b);
               assert(mon[i].a <= a && b <= mon[i].b);
               assert(tmp < a);
               tmp = b;
               v += b-a;
               for (; a < b; ++a)
                  assert(++count[a] <= M);
            }
            assert(v == mon[i].v);
         }
         free( count );
         fgets(buf, sizeof(buf), out);
         printf("\"Yes\" is yes!!\n");
      }
   }
}

Code: Select all

REP(j,I-1) B[j]=ix[j];
REP(i,n) {
	vector<pair<int,int> > sol;
	REP(j,I-1) {
	  int x = F[i][n+j];
	  if(!x) continue;
	  int start=B[j],end=start+x,len=ix[j+1]-ix[j];
	  B[j]=end;
	  if(end<=ix[j+1])
	    sol.push_back(make_pair(start,end));
	  else {
	    sol.push_back(make_pair(start,ix[j+1]));
	    sol.push_back(make_pair(ix[j],end-len)), B[j]-=len;
	  }
	  if(B[j]==ix[j+1]) B[j]=ix[j];
	}
	sort(sol.begin(),sol.end());
	vector<pair<int,int> > r;
	REP(j,size(sol)) {
	  if(size(r) && r.back().second==sol[j].first)
	    r.back().second = sol[j].second;
	  else r.push_back(sol[j]);
	}
	cout << r.size();
	REP(j,size(r))
	  cout << " ("<<r[j].first<<','<<r[j].second<<')';
	cout << endl;
}

Code: Select all

/*start 5.30
*/
#include<iostream>
#include<algorithm>
using namespace std;
#define FOR(i,n) for(int i=0;i<n;++i)
struct Monkey{
    int v,s,e;
    Monkey(){};
}in[110];
const int MAX=400;
int cap[MAX][MAX],fnet[MAX][MAX],mark[MAX],parent[MAX],adj[MAX],deg[MAX],MA=1,out[MAX],outC=0;
int used[50010];
int inter[210],monkeyC;
#define Mon(n) (n+2)
#define Int(n) (2+monkeyC+n)

#define NN MAX // the maximum number of vertices[0,n),[i][j] = i->j edge
int q[NN], qf, qb, prev[NN];// BFS – Q
int FordFulkerson(int s, int t , int n){
    memset( fnet, 0, sizeof( fnet ) );// init the flow network
    int flow = 0;
    while( true ){
        memset( prev, -1, sizeof( prev ) );// find an augmenting path
        qf = qb = 0;
        prev[q[qb++] = s] = -2; //Enqueue
        while( qb > qf && prev[t] == -1 )//BFS //Dequeue
            for( int u = q[qf++], v = 0; v < n; v++ )
                if( prev[v] == -1 && fnet[u][v] < cap[u][v] )
                    prev[q[qb++] = v] = u;
        if( prev[t] == -1 ) break;// see if we're done
        int bot = 0x7FFFFFFF;  
        for( int v = t, u = prev[v]; u >= 0; v = u, u = prev[v] ) // get the bottleneck capacity
           bot = min(bot,cap[u][v]-fnet[u][v]);
        for( int v = t, u = prev[v]; u >= 0; v = u, u = prev[v] )// update the flow network
            fnet[u][v] += bot,fnet[v][u] -= bot;
        flow += bot;
    }
    return flow;
}
int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int n,m,ca=1;
    while(scanf("%d",&n)>0  && n ){
        scanf("%d",&m);
        monkeyC=n;
        FOR(i,n)scanf("%d%d%d",&in[i].v,&in[i].s,&in[i].e );
        FOR(i,n) inter[2*i]=in[i].s ,inter[2*i+1]=in[i].e;
        sort(inter,inter+2*n);
        memset(cap,0,sizeof(cap) );
        int src=0;
        int sink=1;
        //make Graph;
        int Sum=0;
        FOR(i,n)    Sum+=in[i].v;
        FOR(i,n)    cap[src][Mon(i)]=in[i].v;
        FOR(i,n){//monkey
            FOR(j,2*n-1){//interval [ .. )
                if( in[i].s<=inter[j] && inter[j]<in[i].e ){
                    cap[ Mon(i) ][ Int(j) ]= inter[j+1]-inter[j];
        //            printf("[%d][%d] = %d %d %d\n",Mon(i) , Int(j) ,inter[j],inter[j+1], inter[j+1]-inter[j] );
                }
            }
        }
        memset(used,0,sizeof(used) );
        FOR(i,2*n-1)    cap[Int(i) ][sink]=(inter[i+1]-inter[i])*m;
        int res=FordFulkerson(src,sink,Int(2*n) );
        //printf("%d\n",res);
        if(res==Sum){
            printf("Case %d: Yes\n",ca++);
            FOR(i,n){
                //printf("moneyk %d : ",i);
                outC=0;
                FOR(j,2*n-1){
                    if( fnet[ Mon(i)][ Int(j) ]>0  ){
                        int s=inter[j];
                        while( used[s]>=m)s++;
                        FOR(t,fnet[ Mon(i)][Int(j)] ){
                            //printf(">>%d\n",s);
                            used[s]++;
                            out[outC++]=s++;
                            if(outC>1 && out[outC-1]==out[outC-2])outC-=2;
                            out[outC++]=s;
                        }
                        
                    }
                }                
                //FOR(i,outC)printf("%d ",out[i] );
                printf("%d",outC/2);
                FOR(i,outC)printf(" (%d,%d)",out[i],out[i+1] ),++i;
                putchar('\n');
            }
        }
        else 
            printf("Case %d: No\n",ca++);
    }
    return 0;
}

Code: Select all

    #include <cstdio>
    #include <vector>
    #include <bitset>
    #include <algorithm>
    #include <cstring>
    #define NMAX 105
    #define HMAX 405
    #define LMAX 505
    #define INF 1000000000
    #define pb push_back
    #define mp make_pair
    #define vi vector <int>
    #define pii pair <int, int>
    #define x first
    #define y second
    using namespace std;
    int n, m, no, val[HMAX], F[LMAX][LMAX], C[LMAX][LMAX];
    int source, dest, dad[LMAX], flow, expected, Q[LMAX];
    vi G[LMAX], I;
    vector <pii> sol;
    pair <int, pii> info[NMAX];
    bitset <LMAX> vis;

    void add_edge(int from, int to, int cap)
    {
        G[from].pb(to); C[from][to] = cap;
        G[to].pb(from);
    }

    void read()
    {
        int i, j, x, y;
        for (i = 1; i <= n; i++)
        {
            scanf("%d%d%d", &info[i].x, &info[i].y.x, &info[i].y.y);
            expected += info[i].x;  info[i].y.y--;
            I.pb(info[i].y.x); I.pb(info[i].y.y);
        }
        sort(I.begin(), I.end());
        I.erase(unique(I.begin(), I.end()), I.end());
       
        source = 0; no = I.size();
        for (i = 0; i < no - 1; i++)
        {
            val[2 * i + 1] = 1;
            val[2 * i + 2] = I[i + 1] - I[i] - 1;
        }
        val[2 * no - 1] = 1;
       
        for (i = 1; i <= 2 * no; i++)
            add_edge(source, i, val[i] * m);
         
        dest = 2 * no + n + 1;
        for (i = 1; i <= n; i++)
        {
            x = lower_bound(I.begin(), I.end(), info[i].y.x) - I.begin();
            y = lower_bound(I.begin(), I.end(), info[i].y.y) - I.begin();
            info[i].y = mp(2 * x + 1, 2 * y + 1);
           
            for (j = x; j < y; j++)
            {
                add_edge(2 * j + 1, 2 * no + i, val[2 * j + 1]);
                add_edge(2 * j + 2, 2 * no + i, val[2 * j + 2]);
            }
            add_edge(2 * y + 1, 2 * no + i, val[2 * y + 1]);
           
            add_edge(2 * no + i, dest, info[i].x);
        }
    }

    int BF()
    {
        vis.reset();
        Q[Q[0] = 1] = source; vis[source] = 1;
        int i, j, node, x;
        for (i = 1; i <= Q[0]; i++)
        {
            node = Q[i];
            for (j = 0; j < (int)G[node].size(); j++)
            {
                x = G[node][j];
                if (F[node][x] < C[node][x] && !vis[x])
                {
                    Q[++Q[0]] = x; dad[x] = node; vis[x] = 1;
                    if (x == dest)
                        return 1;
                }
            }
        }
       
        return vis[dest];
    }

    void max_flow()
    {
        int node, fmin;
        while (BF())
        {
            fmin = INF;
            for (node = dest; node != source; node = dad[node])
                fmin = min(fmin, C[dad[node]][node] - F[dad[node]][node]);
               
            for (node = dest; node != source; node = dad[node])
            {
                F[dad[node]][node] += fmin;
                F[node][dad[node]] -= fmin;
            }
           
            flow += fmin;
        }
    }

    void recons()
    {
        int i, j, x, y;
        for (i = 1; i <= n; i++)
        {
            for (j = info[i].y.x; j <= info[i].y.y; j++)
                if (F[j][i + 2 * no])
                {
                    x = I[(j - 1) / 2];  y = x + F[j][i + 2 * no];
                    if (!(j & 1))
                        x++, y++;
                       
                    if (sol.size() && sol[sol.size() - 1].y == x)
                        sol[sol.size() - 1].y = y;
                    else
                        sol.pb(mp(x, y));
                }
           
            printf("%d", sol.size());
            for (j = 0; j < (int)sol.size(); j++)
                printf(" (%d,%d)", sol[j].x, sol[j].y);
            printf("\n");
            sol.clear();
        }
    }

    void clear_data()
    {
        I.clear();
        int i;
        for (i = source; i <= dest; i++)
            G[i].clear();
        memset(F, 0, sizeof(F));
        memset(C, 0, sizeof(C));
        expected = flow = 0;
        memset(val, 0, sizeof(val));
    }

    int main()
    {
        //freopen("input", "r", stdin);
        int test_no = 0;
        while (scanf("%d%d", &n, &m), n)
        {
            test_no++;
           
            read();
            max_flow();
            printf("Case %d: ", test_no);
            if (flow == expected)
            {
                printf("Yes\n");
                recons();
            }
            else
                printf("No\n");
           
            clear_data();
        }
        return 0;
    }