Назад к лучшим решениям  Status: AC, problem ZRIS, contest ZEL06. By rem (Renat Mullakhanov), 2006-02-28 17:48:57.
 
#include <map>
#include <set>
#include <cmath>
#include <queue>
#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <numeric>
#include <algorithm>
 
using namespace std;
 
typedef unsigned char uchar;
typedef unsigned int uint;
typedef unsigned short ushort;
typedef long long int64;
typedef unsigned long long uint64;
typedef long double real;
typedef vector<int> vi;
typedef vector<string> vs;
 
template<class T> T sqr(T a){ return a*a; }
 
#define For(i,a,b) for(int i=(a); i<=(b); i++)
#define Rep(i,n) for(int i=0; i<(n); i++)
#define Size(x) (int(x.size()))
#define Ford(i,a,b) for(int i=(a); i>=(b); i--)
#define Repd(i,n) for(int i=(n)-1; i>=0; i--)
#define Fil(a) memset(&a,0,sizeof(a))
#define Filn(a,n) memset(a,0,(n)*sizeof(a[0]))
#define Cpy(a,b) memcpy(&a,&b,sizeof(a))
#define Mp(x,y) make_pair(x,y)
#define All(v) (v).begin(),(v).end()
#define Foreach(it,v) for(typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define Fordeach(it,v) for(typeof((v).rbegin()) it=(v).rbegin(); it!=(v).rend(); ++it)
 
#ifdef ONLINE_JUDGE
    #define SINT64 "%lld"
#else
    #define SINT64 "%I64d"
#endif
 
const int DEPTH_LIMIT=100;
 
int n;
int am[1024][1024],amrow[1024],amcol[1024];
vi vi1,vj1,vi2,vj2;
 
inline void addrect(int i1,int j1,int i2,int j2)
{
    vi1.push_back(i1);
    vj1.push_back(j1);
    vi2.push_back(i2);
    vj2.push_back(j2);
    int n=i2-i1+1;
    int m=j2-j1+1;
    --am[n][m]; --amrow[n]; --amcol[m];
    if(m!=n)
    {
        --am[m][n]; --amrow[m]; --amcol[n];
    }
}
 
const int THRESHOLD=1000;
int dp[THRESHOLD+1];
 
int horiz(int n,int m,bool fill,int si,int sj)
{
    if(amrow[n]==0) return 0;
    if(m>THRESHOLD)
    {
        int s=m;
        int from=sj;
        Ford(i,m,1)
            if(i>s) i=s+1;
            else if(am[n][i]>0)
            {
                int k=min(am[n][i],s/i);
                if(!fill) s-=k*i;
                else
                {
                    while(k--)
                    {
                        s-=i;
                        addrect(si,from,si+n-1,from+i-1);
                        from+=i;
                    }
                }
            }
        return m-s;
    }
    else
    {
        For(i,0,m) dp[i]=-1;
        dp[0]=0;
        Ford(i,m,1) 
        {
            if(dp[m]!=-1) break;
            Repd(z,am[n][i])
            {
                bool changes=false;
                Ford(j,m,i) if(dp[j]==-1 && dp[j-i]!=-1)
                {
                    changes=true;
                    dp[j]=i;
                }
                if(!changes || dp[m]!=-1) break;
            }
        }
        int k=m;
        while(dp[k]==-1) --k;
        int ret=k;
        if(fill)
        {
            int from=sj;
            while(k>0)
            {
                addrect(si,from,si+n-1,from+dp[k]-1);
                from+=dp[k];
                k-=dp[k];
            }
        }
        return ret;
    }
}
 
int vert(int n,int m,bool fill,int si,int sj)
{
    if(amcol[m]==0) return 0;
    if(n>THRESHOLD)
    {
        int s=n;
        int from=si;
        Ford(i,n,1)
            if(i>s) i=s+1;
            else if(am[i][m]>0)
            {
                int k=min(am[i][m],s/i);
                if(!fill) s-=k*i;
                else
                {
                    while(k--)
                    {
                        s-=i;
                        addrect(from,sj,from+i-1,sj+m-1);
                        from+=i;
                    }
                }
            }
        return n-s;
    }
    else
    {
        For(i,0,n) dp[i]=-1;
        dp[0]=0;
        Ford(i,n,1) 
        {
            if(dp[n]!=-1) break;
            Repd(z,am[m][i])
            {
                bool changes=false;
                Ford(j,n,i) if(dp[j]==-1 && dp[j-i]!=-1)
                {
                    changes=true;
                    dp[j]=i;
                }
                if(!changes || dp[n]!=-1) break;
            }
        }
        int k=n;
        while(dp[k]==-1) --k;
        int ret=k;
        if(fill)
        {
            int from=si;
            while(k>0)
            {
                addrect(from,sj,from+dp[k]-1,sj+m-1);
                from+=dp[k];
                k-=dp[k];
            }
        }
        return ret;
    }
}
 
void solve(int si,int sj,int n,int m,int depth)
{
    //assert(1<=n && n<=1000 && 1<=m && m<=1000);
    if(depth>DEPTH_LIMIT)
    {
        int s1=n*horiz(n,m,false,si,sj);
        int s2=m*vert(n,m,false,si,sj);
        if(s1>s2) horiz(n,m,true,si,sj);
        else vert(n,m,true,si,sj);
        return;
    }
    if(horiz(n,m,false,si,sj)==m) 
    {
        assert(horiz(n,m,true,si,sj)==m);
        return;
    }
    if(vert(n,m,false,si,sj)==n)
    {
        assert(vert(n,m,true,si,sj)==n);
        return;
    }
    Rep(q,2)
    {
        if((n>m)^q)
        {
            int mx,k;
            mx=k=0;
            Ford(i,n,1) 
            {
                //if(m*i<=mx*k) break;
                int cur=horiz(i,m,false,si,sj);
                if(cur>mx)
                {
                    mx=cur;
                    k=i;
                    if(mx==m) break;
                }
            }
            if(mx>0) 
            {
                assert(horiz(k,m,true,si,sj)==mx);
                if(mx<m) solve(si,sj+mx,k,m-mx,depth+1);
                if(k<n) solve(si+k,sj,n-k,m,depth+1);
                return;
            }
        }
        else
        {
            int mx,k;
            mx=k=0;
            Ford(j,m,1)
            {
                //if(n*j<=mx*k) break;
                int cur=vert(n,j,false,si,sj);
                if(cur>mx)
                {
                    mx=cur;
                    k=j;
                    if(mx==n) break;
                }
            }
            if(mx>0)
            {
                assert(vert(n,k,true,si,sj)==mx);
                if(mx<n) solve(si+mx,sj,n-mx,k,depth+1);
                if(k<m) solve(si,sj+k,n,m-k,depth+1);
                return;
            }
        }
    }
}
 
void gener(int tests,int n)
{
    srand(123);
    freopen("input.txt","wt",stdout);
    printf("%d\n",tests);
    while(tests--)
    {
        printf("%d\n",n);
        int k=rand()%50;
        printf("%d\n",k);
        while(k--) printf("%d %d %d\n",rand()%n+1,rand()%n+1,rand()%5+1);
    }
    exit(0);
}
 
bool filled[1024][1024];
 
void check()
{
    int cnt=0;
    For(i,1,n) For(j,1,n) filled[i][j]=false;
    Rep(q,Size(vi1))
    {
        assert(1<=vi1[q] && vi1[q]<=vi2[q] && vi2[q]<=n);
        assert(1<=vj1[q] && vj1[q]<=vj2[q] && vj2[q]<=n);
        For(i,vi1[q],vi2[q]) For(j,vj1[q],vj2[q])
        {
            assert(!filled[i][j]);
            filled[i][j]=true;
            ++cnt;
        }
    }
    printf("%d of %d\n",cnt,n*n);
}
 
void outtest()
{
    printf("n=%d\n",n);
    For(i,1,n) For(j,1,i) if(am[i][j]>0)
        printf("%d %d %d\n",i,j,am[i][j]);
}
 
int main()
{
    //gener(10,1000);
 
#ifndef ONLINE_JUDGE
    freopen("input.txt","rt",stdin);
    freopen("output.txt","wt",stdout);
#endif
 
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        For(i,1,n) 
        {
            Filn(am[i],n+1);
            amrow[i]=amcol[i]=0;
        }
        int k;
        scanf("%d",&k);
        while(k--)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            //assert(1<=x && x<=n && 1<=y && y<=n);
            //assert(z>0 && am[x][y]+z<=1000000000);
            am[x][y]+=z;
            amrow[x]+=z;
            amcol[y]+=z;
            if(x!=y) 
            {
                am[y][x]+=z;
                amrow[y]+=z;
                amcol[x]+=z;
            }
        }
        vi1.clear(); vj1.clear();
        vi2.clear(); vj2.clear();
        //outtest();
        solve(1,1,n,n,1);
        printf("%d\n",Size(vi1));
        Repd(i,Size(vi1)) printf("%d %d %d %d\n",vi1[i],vj1[i],vi2[i],vj2[i]);
        //check();
    }
 
    exit(0);
}